How We Coding

[1149] RGB 거리

BOJ/DP2018. 1. 30. 21:52

http://boj.kr/1149


기본 DP2


- d[n][k] : n번째 집을 컬러 k로 칠했을 때, 1~n번째 집을 칠하는데 드는 최소비용.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
 
int rgb[1001][3];
int d[1001][3];
 
int min(int a, int b)
{
    return a > b ? b : a;
}
 
int go(int n, int k)
{
    int ans;
 
    if(n == 0) return rgb[0][k];
    if(d[n][k]) return d[n][k];
 
    if(k == 0) {
        ans = go(n-1, 1);
        ans = min(ans, go(n-1, 2));
    }
    else if(k == 1) {
        ans = go(n-1, 0);
        ans = min(ans, go(n-1, 2));
    }   
    else {
        ans = go(n-1, 0);
        ans = min(ans, go(n-1, 1));
    }
    return d[n][k] = ans + rgb[n][k];
}
 
int main()
{
    int i, j, n;
    int ans;
    scanf("%d", &n);
    
    for(i=0; i<n; i++)
        for(j=0; j<3; j++)
            scanf("%d", &rgb[i][j]);;
 
    ans = go(n-1, 0);
    ans = min(ans, go(n-1, 1));
    ans = min(ans, go(n-1, 2));
    printf("%d\n", ans);
 
    return 0;
}
cs



>> 실은 6개월전에 해결했던 문제다.

     하지만 과거에 코드를 보니, 한동안 ps를 안해서 그런지 더 멍청해진것 같다는 생각이 든다...


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
 
int rgb[1001][3], d[1001][3];
 
int min(int a, int b)
{
    return a > b ? b : a;
}
 
int go(int n, int color)
{
    int ret;
    if(n < 0) return 0; 
    if(d[n][color]) return d[n][color];    
    ret = go(n-1, (color+1)%3);
    ret = min(ret, go(n-1, (color+2)%3));    
    return d[n][color] = ret+rgb[n][color];
}
 
int main()
{
    int i, j, n, ans;
    scanf("%d", &n);
 
    for(i=0; i<n; i++) 
        for(j=0; j<3; j++) 
            scanf("%d", &rgb[i][j]);
    
    ans = go(n-1, 2);
    ans = min(ans, go(n-1, 1)); 
    ans = min(ans, go(n-1, 0)); 
    printf("%d\n", ans);
    return 0;
}
cs


- 백준해설 


i번째 집의 이웃은 i-1번째 집과 i+1번째 집. (연속)

처음집과 마지막 집은 이웃이 아니다..!!


다이나믹에서 중요한 조건중에 하나인 "연속"이라는 조건이 포함된 문제..!!

앞의 집과의 색만 다르게 칠하면 된다.



- 아래 코드는 바텀업.


1
2
3
4
5
6
7
for(int i=1; i<=n; i++) {
    d[i][0] = min(d[i-1][1], d[i-1][2]) + a[i][0];
    d[i][1] = min(d[i-1][0], d[i-1][2]) + a[i][0];
    d[i][2] = min(d[i-1][0], d[i-1][1]) + a[i][0];
}
 
cout << min({d[n][0], d[n][1], d[n][2]}) << '\n';
cs

>> 0번째는 비워두고 하는것이 좋다. 

>> min({a, b, c}); // a, b, c 중 최소값. 

>> c++11 문법으로 아래가 함수의 원형인 것 같다. 즉 리스트로 들어가서 그 리스트들 중 최소값이 

     리턴되는 방식인 것 같다.


template<class T>
T min( std::initializer_list<T> ilist)
{
    return *std::min_element(ilist.begin(), ilist.end());
}


'BOJ > DP' 카테고리의 다른 글

[2302] 극장 좌석  (0) 2018.02.05
[1937] 욕심쟁이 판다  (0) 2018.02.01
[1309] 동물원  (0) 2018.02.01
[1932] 숫자삼각형  (0) 2018.02.01
[1463] 1로 만들기  (0) 2018.01.26

<1-3> 연산자

Language/Python2018. 1. 30. 08:31

동영상 강의 : http://pythonkim.tistory.com/notice/77


# Day_01_02_Operator.py


# 연산자 : 산술, 관계, 논리, 비트



- 산술 : +    -    *    /    //    %    **    


1
2
3
4
5
6
7
8
9
# 산술 : +    -    *    /    //   %   **
a, b = 17, 5
print(a+b)      # 22
print(a-b)      # 12
print(a*b)      # 85
print(a/b)      # 3.4
print(a//b)     # 3
print(a%b)      # 2 , mod
print(a**b)     # 1419857, 17^5
cs


# 문제


1
2
3
4
5
6
n = 37
a1 = n//10
a2 = n%10
 
n = a2*10 + a1
print(n)    # 73
cs



- 관계 : >    >=    <    <=    ==    !=


1
2
3
4
5
6
7
8
9
10
11
# 관계 : > >= < <= == !=
 
a, b = 17, 5
print(a, b)
 
print(a > b)    # T
print(a >= b)   # T
print(a < b)    # F
print(a <= b)   # F
print(a == b)   # F
print(a != b)   # T
cs

- 단어에도 대소가 있다. >> 아스키 코드로 비교.

- 대문자보다 소문자가 크다.

- 한글은 유니코드 사용

- True 나 False 도 숫자로 이루어져 있다.

>> 데이터 변환을 통해 확인.


# 형변환(casting) : int    float    str    bool


1
2
3
4
5
6
7
# 형변환(casting) : int, float, str, bool
 
print(int(True))    # 1
print('345')        # 345
print(int('345'))   # 345
print(int(a != b))  # 1
print(int(False))   # 0
cs

# 문제

# 10대인지 판단해보기.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 문제
# 10대인지 판단해보기.
 
age = 15
b1 = age >= 10      # T, F
b2 = age <= 19      # T, F
 
# T * T = T
# T * F = F
# F * T = F
# F * F = F
 
print(bool(b1*b2))  # True
print(age >= 10  *  age <= 19)    # False
print((age >= 10) * (age <= 19))    # 1
print(10 <= age <= 19)      # True (python only)

cs




- 논리 : and    or    not

>> 관계 연산자를 묶을 때 사용한다.


1
2
3
4
5
6
7
8
# 논리 : and  or  not
 
print(True and True)    # True
print(True and False)    # False
print(False and True)    # False
print(False and False)    # False
 
print(age >= 10  and  age <= 19)    # True

cs


- 비트 연산자는 pass



'Language > Python' 카테고리의 다른 글

<1-7> 정규표현식 with Python  (0) 2018.02.03
<1-6> 정규표현식 (Regular Expression)  (0) 2018.02.02
<1-5> 함수(function)  (0) 2018.02.01
<1-4> 제어문(if)  (0) 2018.01.31
<1-2> 파이썬 입문  (0) 2018.01.29

<1-1> How To Play River Flows In You On Guitar (arranged by Sunga Jung) (guitar lesson / tutorial) Part 1

Play the guitar.2018. 1. 29. 18:37


How To Play River Flows In You On Guitar (arranged by Sunga Jung) (guitar lesson / tutorial) Part 1


Tutorial : https://www.youtube.com/watch?v=f4KKQUf7bQc


Fret, String


2 CaFo


3F1S, 2F4S : 1, 4 together


2F1S, 2F4S : 1, 3 together


3F1S, 2F4S : 1, 2 together


2F1S, 2F4S : 1, 3 together



3F1S,  3F2S, 3F5S : 1, 5 together


3F1S,  3F2S, 3F5S : 2, 3 together


3F1S,  1F2S : 1


3F1S,  1F2S : 2, 3 together


2, 3 and repeat.



2, 3


3F1S, 2F4S : 1, 4 together


2F1S, 2F4S : 1, 3 together


3F1S : 1


2F4S : 4 then 2


2F1S : 1, 3 together


3F1S : 1


3F1S,  3F2S, 3F5S : 5 then 3 then 2 then 1


1F2S, 3F4F : 5 then 3 then 2




3F3S, 3F6S : 3, 6 together


4F3S : 3


1F2S : 2 (index finger)


3F2S : 4, 3, 2, toghether quickly


2


2F3S : 4, 3 together





'Play the guitar.' 카테고리의 다른 글

시대를 초월할 마음 Ep.01-02  (0) 2018.03.24
<1-2> How To Play "River Flows In You" On Guitar (arranged by Sunga Jung) (guitar lesson / tutorial) Part 2  (0) 2018.02.12

티스토리툴바