How We Coding

[9184] 신나는 함수 실행

BOJ/DP2018. 2. 16. 21:47

http://boj.kr/9184


- 메모이제이션만 하면 된다.


< 소스코드 >


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
#include <stdio.h>
 
int d[21][21][21];
 
int w(int a, int b, int c)
{
    if(a <= 0 || b <= 0 || c <= 0) return 1;
 
    if(a > 20 || b > 20 || c > 20) 
        return w(20, 20, 20);
    
    if(d[a][b][c]) return d[a][b][c];
    
    if(a < b && b < c)
        return d[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
    
    return d[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
}
 
int main()
{
    while(1) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if(a == -1 && b == -1 && c == -1) break;
        
        printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
    }
    return 0;
}
 
cs


>> 12 라인을 9번 라인보다 먼저 써서 런타임에러가 발생했었다...

>> 배열의 각 차원의 크기는 21인데, a, b, c 중 20보다 큰 값이 들어오면 저 코드를 먼저 실행하게 

     되어 런타임 에러가 발생하는 듯 하다.

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

[2216] 문자열과 점수  (0) 2018.02.21
[11048] 이동하기  (0) 2018.02.18
[2302] 극장 좌석  (0) 2018.02.05
[1937] 욕심쟁이 판다  (0) 2018.02.01
[1309] 동물원  (0) 2018.02.01

[2302] 극장 좌석

BOJ/DP2018. 2. 5. 17:47

http://boj.kr/2302


d[n] : VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수


- 소스코드


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
#include <stdio.h>
 
int vip[41], d[41];
 
int go(int k)
{
    int ret;
    if(k == 0 || k == 1) return 1; 
    if(d[k]) return d[k];
    if(vip[k]) return d[k] = go(k-1);
 
    ret = go(k-1);
    if(!vip[k-1]) ret += go(k-2);
    
    return d[k] = ret;
}
 
int main()
{
    int n, m, k;
    scanf("%d%d", &n, &m);
 
    while(m--) {
        scanf("%d", &k);
        vip[k] = 1;
    }
 
    printf("%d\n", go(n));
    return 0;
}
cs


>> n이 n번에 앉았을 때의 경우의 수 : d[n-1] 

>> n이 n-1에 앉았을 때의 경우의 수 : d[n-2]


>> 여기서는 10번 라인을 쓰지 않으면, n-1번이 vip석이 아닌경우 n번이 vip석이여도 n-1과 n번이 

     바꿔 앉는 경우를 세어 중복이 발생한다.

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

[11048] 이동하기  (0) 2018.02.18
[9184] 신나는 함수 실행  (0) 2018.02.16
[1937] 욕심쟁이 판다  (0) 2018.02.01
[1309] 동물원  (0) 2018.02.01
[1932] 숫자삼각형  (0) 2018.02.01

[1937] 욕심쟁이 판다

BOJ/DP2018. 2. 1. 21:42

http://boj.kr/1937


d[r][c] : (r, c)에서 대나무를 먹기 시작했을 때, 판다가 살 수 있는 최대 일수.


- 소스코드


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
#include <stdio.h>
 
int n;
int g[505][505];
int d[505][505];
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int go(int r, int c)
{
    int i, ret=1;
    
    if(d[r][c]) return d[r][c];
 
    for(i=0; i<4; i++) {
        int nr = r+dr[i];
        int nc = c+dc[i];
        if(g[r][c] < g[nr][nc]) {
            ret = max(ret, go(nr, nc)+1);
        }
    }
    return d[r][c] = ret;
}
 
int main()
{
    int i, j, ans = 0;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            scanf("%d", &g[i][j]);
 
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            ans = max(ans, go(i, j));
    printf("%d\n", ans);
    return 0;
}
cs


>> 오타때문에 두번 틀렸다...ㅜㅜ

>> 좌표를 (1,1) 부터 시작하고 사이즈를 505로 넉넉하게 잡으면, 좌표를 벗어날 일이 없다.

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

[9184] 신나는 함수 실행  (0) 2018.02.16
[2302] 극장 좌석  (0) 2018.02.05
[1309] 동물원  (0) 2018.02.01
[1932] 숫자삼각형  (0) 2018.02.01
[1149] RGB 거리  (0) 2018.01.30

[1309] 동물원

BOJ/DP2018. 2. 1. 20:23

http://boj.kr/1309


d[n][k] : n번째 줄에 상태가 k일 때, 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
#include <stdio.h>
#define MOD 9901
 
int d[100001][3];
 
int go(int n, int k)
{
    int a, b;
    if(n == 0) return 1;
    if(d[n][k]) return d[n][k];
 
    a = go(n-1, (k+1)%3);
    b = go(n-1, (k+2)%3);
    
    if(k == 0) a += go(n-1, 0);
 
    return d[n][k] = (a+b)%MOD; 
}
 
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", go(n, 0));
    return 0;
}
cs


>> k = 0 인 경우는 둘 다 비워있는 상태.

>> k = 1 인 경우는 사자를 왼쪽에 배치, k = 2 인 경우는 사자를 오른쪽에 배치한 상태



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

[2302] 극장 좌석  (0) 2018.02.05
[1937] 욕심쟁이 판다  (0) 2018.02.01
[1932] 숫자삼각형  (0) 2018.02.01
[1149] RGB 거리  (0) 2018.01.30
[1463] 1로 만들기  (0) 2018.01.26

[1932] 숫자삼각형

BOJ/DP2018. 2. 1. 12:17

http://boj.kr/1932


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
#include <stdio.h>
#include <string.h>
 
int g[505][505];
int d[505][505];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int go(int n, int k)
{
    int L, R;
    if(n == 0 || k == 0) return 0;
 
    if(d[n][k] != -1) return d[n][k];
 
    L = go(n-1, k-1);
    R = go(n-1, k);
    return d[n][k] = g[n][k] + max(L, R);
}
 
int main()
{
    int i, j, n;
    int ans=0;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++) 
        for(j=1; j<=i; j++) 
            scanf("%d", &g[i][j]);
 
    memset(d, -1, sizeof(d));
 
    for(i=1; i<=n; i++)
        ans = max(ans, go(n, i));
    printf("%d\n", ans);
 
    return 0;
}
cs


>> 위의 줄 오른쪽 대각선의 k값은 현재 줄의 k값과 동일하며,

>> 위의 줄 왼쪽 대각선의 k값은 현재 줄의 k-1값과 동일.

>> k는 1부터 시작, g[n][0] = 0 인점을 이용.



- 아래 코드는 바텀업


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
#include <stdio.h>
 
int n, g[501][501], d[501][501];
 
int main()
{
    int i, j, ans;
    scanf("%d", &n);
    
    for(i=1; i<=n; i++)
        for(j=1; j<=i; j++)
            scanf("%d", &g[i][j]);
 
    d[1][1] = g[1][1];
 
    for(i=2; i<=n; i++) {
        for(j=1; j<=i; j++) {
            d[i][j] = d[i-1][j-1] > d[i-1][j] ? d[i-1][j-1] : d[i-1][j];
            d[i][j] += g[i][j];
        }
    }
 
    ans = d[n][1];
    for(i=2; i<=n; i++)
        if(ans < d[n][i])
            ans = d[n][i];
 
    printf("%d\n", ans);
    return 0;
}
cs


>> 1년전에 푼 코드이고, 분명 직접 생각해내서 푼 기억은 있다.

>> 근데 보통 DP를 풀때 대부분의 문제를 탑다운으로 푸는데,,, 바텀업으로 풀려있다.

>> 코드의 원리는 위에서 설명한 아이디어와 동일하다.

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

[2302] 극장 좌석  (0) 2018.02.05
[1937] 욕심쟁이 판다  (0) 2018.02.01
[1309] 동물원  (0) 2018.02.01
[1149] RGB 거리  (0) 2018.01.30
[1463] 1로 만들기  (0) 2018.01.26

[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

[1463] 1로 만들기

BOJ/DP2018. 1. 26. 11:24

http://boj.kr/1463


DP1 - basic


- go(n) : 3개의 연산을 적절히 사용했을 때, n을 1로 만드는 회수의 최소값.


< 소스코드 - top down >


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
#include <stdio.h>
#define INF 0x3f3f3f3f
 
int d[1000001];
 
int go(int n)
{
    int a, b, c, ans;
    a = b = c = INF;
    if(n == 1) return 0;
    if(d[n]) return d[n];
 
    if(n%3 == 0) a = go(n/3)+1;
    if(n%2 == 0) b = go(n/2)+1;
    c = go(n-1)+1;
    ans = a < b ? a : b;
    ans = ans < c ? ans : c;
    return d[n] = ans;
}
 
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", go(n));
    return 0;
}
cs


< 소스코드 - bottom up >

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
 
int main()
{
    int i, n, d[1000001];
    scanf("%d", &n);
    
    d[1] = 0;
 
    for(i=2; i<=n; i++) {
        d[i] = d[i-1] + 1;
        if(i%2 == 0 && d[i] > d[i/2]+1)
            d[i] = d[i/2]+1;
        if(i%3 == 0 && d[i] > d[i/3]+1)
            d[i] = d[i/3]+1;
    }
    
    printf("%d\n", d[n]);
    return 0;
}
 
 
cs


-

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

[2302] 극장 좌석  (0) 2018.02.05
[1937] 욕심쟁이 판다  (0) 2018.02.01
[1309] 동물원  (0) 2018.02.01
[1932] 숫자삼각형  (0) 2018.02.01
[1149] RGB 거리  (0) 2018.01.30

티스토리툴바