How We Coding

[9252] LCS2

BOJ/DP2018. 4. 22. 02:07

[9252] LCS2 : http://boj.kr/9252



### DP -Track ### (참고 : https://kks227.blog.me/221028710658)


< 소스코드 >


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
50
51
52
53
54
55
56
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
 
struct P { int ret, si; };
 
char s[1001], t[1001];
int d[1001][1001];
char a[1001];
 
stack<P> st;
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int lcs2(int si, int ti)
{
    int ret = 0; 
 
    if(si < 0 || ti < 0) return 0;
    if(d[si][ti] != -1) return d[si][ti];
 
    if(s[si] == t[ti]) {
        ret = lcs2(si-1, ti-1)+1;
        st.push((P){ret, si});
    }
    else {
        ret = max(lcs2(si-1, ti), lcs2(si, ti-1));
    }   
    return d[si][ti] = ret;
}
 
int main()
{
    int sLen=0, tLen=0;
    scanf("%s%s", s, t);
 
    while(s[sLen]) sLen++;
    while(t[tLen]) tLen++;
 
    memset(d, -1, sizeof(d));
 
    int ans = lcs2(sLen-1, tLen-1);
    printf("%d\n", ans);
 
    while(!st.empty()) {
        if(st.top().ret == ans) {
            a[--ans] = s[st.top().si];
        }
        st.pop();
    }
    puts(a);
}
cs


>> 아이디어는 부분문제의 답을 통해 역으로 그 답을 끼워 맞춘다.


>> 테스트 케이스는 아래와 같다.

ACAYKP

CAPCAK


>> 위 테케에 대한 아웃풋은 아래와 같다.

4

ACAK


>> 위 코드의 경우, 스택 st의 ret 에는 3 4 2 1 3 2 1 가 저장이 된다. 

>> 맨 처음 정답에 해당하는 4일때의 si, 그다음 작은 숫자인 3일때의 si, ...

>> 이렇게 문자를 거꾸로 저장한 다음 출력하면 답이 된다.



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

[9177] 단어 섞기  (0) 2018.05.22
[2602] 돌다리 건너기  (0) 2018.05.17
[9251] LCS  (0) 2018.04.21
[14002] 가장 긴 증가하는 부분 수열 4  (0) 2018.04.18
[10942] 팰린드롬?  (0) 2018.02.22

[9251] LCS

BOJ/DP2018. 4. 21. 02:14

[9251] LSC : http://boj.kr/9251


### DP ###


lcs(si, ti) : 문자열 s의 si번째 문자까지, t의 ti번째의 문자까지의 가장 긴 증가하는 부분 문자열 (최장 공통 부분 수열)


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
#include <stdio.h>
#include <string.h>
 
char s[1001], t[1001];
int d[1001][1001];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int lcs(int si, int ti)
{
    int ret = 0; 
 
    if(si < 0 || ti < 0) return 0;
    if(d[si][ti] != -1) return d[si][ti];
 
    if(s[si] == t[ti]) {
        ret = lcs(si-1, ti-1)+1;
    }
    else {
        ret = max(lcs(si-1, ti), lcs(si, ti-1));
    }   
    return d[si][ti] = ret;
}
 
int main()
{
    int sLen=0, tLen=0;
    scanf("%s%s", s, t);
 
    while(s[sLen]) sLen++;
    while(t[tLen]) tLen++;
 
    memset(d, -1, sizeof(d));
    printf("%d\n", lcs(sLen-1, tLen-1));
    return 0; 
}
cs


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

[2602] 돌다리 건너기  (0) 2018.05.17
[9252] LCS2  (0) 2018.04.22
[14002] 가장 긴 증가하는 부분 수열 4  (0) 2018.04.18
[10942] 팰린드롬?  (0) 2018.02.22
[1890] 점프  (0) 2018.02.22

[14002] 가장 긴 증가하는 부분 수열 4

BOJ/DP2018. 4. 18. 18:36

[14002] 가장 긴 증가하는 부분 수열 4 : http://boj.kr/14002


< 소스코드 >


lis(s) : s 번째에서 시작하는 가장 긴 증가하는 부분 수열 


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
50
51
52
53
54
55
56
57
58
#include <stdio.h>
#include <string.h>
 
int n;
int a[1001], d[1001];
int next[1001];
 
int lis(int s)
{
    int ret=0;
 
    if(d[s]) return d[s];
 
    for(int i=s+1; i<n; i++) {
        if(a[s] < a[i]) {
            int cur = lis(i);
            if(ret < cur) {
                ret = cur;
                next[s] = i;
            }
        }
    }
    return d[s] = ret+1;
}
 
void path(int k)
{
    if(k == -1) return ;
    printf("%d ", a[k]);
    path(next[k]);
}
 
 
int main()
{
    int k, ans=0;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        scanf("%d", a+i);
 
    memset(next, -1, sizeof(next));
 
    for(int i=0; i<n; i++) {
        int tmp = lis(i);
        if(ans < tmp) {
            ans = tmp;
            k = i;
        }
    }
 
    printf("%d\n", ans); 
    path(k);
    puts("");
 
    return 0;
}
 
cs


>> next[i] 는 i의 다음 수열에 해당하는 인덱스.

>> n 제한이 1000 이라, O(n^2) 인 재귀로 가능하다.

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

[9252] LCS2  (0) 2018.04.22
[9251] LCS  (0) 2018.04.21
[10942] 팰린드롬?  (0) 2018.02.22
[1890] 점프  (0) 2018.02.22
[2216] 문자열과 점수  (0) 2018.02.21

[14890] 경사로

BOJ/SWEA2018. 3. 6. 18:11

[14890] 경사로 (http://boj.kr/14890)



right() 에서 L = 2 인경우


3 2 2 2 3 


3 2 2 1 1


x x 3 2 2 (마지막 위치)


2 2 3 


3 3 3


위 경우에 대해서 잘 처리해주면 된다. 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stdio.h>
 
int N, L, ans=0;
int g[101][101];
 
int down(int r, int c)
{
    int curH;
    if(r == N-1) return 1;
 
    curH = g[r][c];
    if(r+L < N && curH-g[r+L][c] == 1) {
        int flag = 1;
        for(int i=1; i<L; i++) {
            if(g[r+L][c] != g[r+i][c])
                flag = 0;
        }
        if(flag){
            if(r+L == N-1) return 1;
            if(g[r+L][c] == g[r+L+1][c])
                return down(r+L+1, c);
            if(g[r+L][c] == g[r+L+1][c]+1)
                return down(r+L, c);
        }
    }
    if(r+L < N && g[r+L][c]-curH == 1) {
        int flag = 1;
        for(int i=1; i<L; i++) {
            if(curH != g[r+i][c])
                flag = 0;
        }
        if(flag) return down(r+L, c);
    }
    if(g[r+1][c] == curH) return down(r+1, c);
    return 0;
}
 
int right(int r, int c)
{
    int curH;
    if(c == N-1) return 1;
 
    curH = g[r][c];
    if(c+L < N && g[r][c+L]-curH == 1) {
        int flag = 1;
        for(int i=1; i<L; i++) {
            if(curH != g[r][c+i])
                flag = 0;
        }
        if(flag) return right(r, c+L);
    }
    if(c+L < N && curH-g[r][c+L] == 1) {
        int flag = 1;
        for(int i=1; i<L; i++) {
            if(g[r][c+L] != g[r][c+i])
                flag = 0;
        }
        if(flag) {
            if(c+L == N-1) return 1;
            if(g[r][c+L] == g[r][c+L+1])
                return right(r, c+L+1);
            if(g[r][c+L] == g[r][c+L+1]+1)
                return right(r, c+L);
        }
    }
    if(g[r][c+1] == curH) return right(r, c+1);
    return 0;
}
 
int main()
{
    scanf("%d%d", &N, &L);
 
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            scanf("%d", &g[i][j]);
 
    for(int i=0; i<N; i++) {
        if(down(0, i)) ans++;
        if(right(i, 0)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}
 
cs


>> 깔끔하게 경우의 수를 펜으로 써가며 확인했으면 금방 했을텐데, 괜히 머릿속으로 한다고 하다가, 시간만 많이 썼다...

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

[14889] 스타트와 링크  (0) 2018.02.28
[14888] 연산자 끼워넣기  (0) 2018.02.27

[14889] 스타트와 링크

BOJ/SWEA2018. 2. 28. 14:14


- [14889] 스타트와 링크 (http://boj.kr/14889)


<소스코드>


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
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
 
int n, ans=1e9;
int g[21][21];
int start[11], link[11];
 
int min(int a, int b)
{
    return a < b ? a : b;
}
 
int abs(int k)
{
    return k > 0 ? k : -k;
}
 
void go(int k, int ti, int ki)
{
    if(ti == n/2 || ki == n/2) {
        int S=0, L=0;
        if(ti == n/2) {
            while(k)
                link[ki++] = k--;
        }
        if(ki == n/2) {
            while(k)
                start[ti++] = k--;
        }
        
        for(int i=0; i<ki; i++) {
            for(int j=i+1; j<ki; j++) {
                S += (g[start[i]][start[j]] + g[start[j]][start[i]]);
                L += (g[link[i]][link[j]] + g[link[j]][link[i]]);
            }
        }
        ans = min(ans, abs(S-L));
        return ;
    }
 
    start[ti] = k;
    go(k-1, ti+1, ki);
 
    link[ki] = k;
    go(k-1, ti, ki+1);
}
 
int main()
{
    int i, j;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            scanf("%d", &g[i][j]);
 
    go(n, 0, 0); 
    printf("%d\n", ans);
    return 0;
}
 
cs


>> 한명씩 스타트에 넣고, 링크에 넣다가 둘중에 한 팀이 절반이 차면 나며지를 다른 팀에 마저 채운다. 그리고 계산!!

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

[14890] 경사로  (0) 2018.03.06
[14888] 연산자 끼워넣기  (0) 2018.02.27

[14888] 연산자 끼워넣기

BOJ/SWEA2018. 2. 27. 20:54

[14888] 연산자 끼워넣기 (http://boj.kr/14888)



1) Brute Force 풀이


< 소스코드 >


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
50
51
52
#include <stdio.h>
 
int a[15], op[4];
 
int ansN = 1e9;
int ansX = -1e9;
int set[15];
 
void go(int n, int ps, int mi, int mu, int dv)
{
    if(n == 1) {
        int ans = a[1];
        for(int i=2; set[i]; i++) {
            if(set[i] == 1) ans += a[i];
            else if(set[i] == 2) ans -= a[i];
            else if(set[i] == 3) ans *= a[i];
            else {
                if(ans < 0) {
                    ans *= -1;
                    ans /= a[i];
                    ans *= -1;
                }
                else
                    ans /= a[i];
            }
        }
        if(ans > ansX) ansX = ans;
        if(ans < ansN) ansN = ans;
    }
 
    if(ps) { set[n]=1; go(n-1, ps-1, mi, mu, dv); }
    if(mi) { set[n]=2; go(n-1, ps, mi-1, mu, dv); }
    if(mu) { set[n]=3; go(n-1, ps, mi, mu-1, dv); }
    if(dv) { set[n]=4; go(n-1, ps, mi, mu, dv-1); }
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<4; i++)
        scanf("%d", op+i);
 
    go(n, op[0], op[1], op[2], op[3]);
    printf("%d\n%d\n", ansX, ansN);
    return 0;
}
 
cs


>> 연산자 순서의 모든 경우의 수를 저장해 놓고, 그 순서에 맞게 계산을 한 다음 최대값과 최소값을 구한다.



2) DP 풀이


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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
 
int a[15], op[4];
int d[15][15][15][15][15];
int e[15][15][15][15][15];
const int INF=1e9;
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int min(int a, int b)
{
    return a < b ? a : b;
}   
 
int maxV(int n, int ps, int mi, int mu, int dv)
{
    int ans = -INF;
    if(n == 1) return a[n];
    if(d[n][ps][mi][mu][dv]!=INF+1) return d[n][ps][mi][mu][dv];
 
    if(ps) ans = max(ans, maxV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = max(ans, maxV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = max(ans, maxV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = maxV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) { 
            tmp *= -1;
            tmp /= a[n];
            tmp *= -1;
        }
        else
            tmp /= a[n];
        ans = max(ans, tmp);
    }
    return d[n][ps][mi][mu][dv] = ans;
}
 
int minV(int n, int ps, int mi, int mu, int dv)
{
    int ans = INF;
    if(n == 1) return a[n];
    if(e[n][ps][mi][mu][dv]!=INF+1) return e[n][ps][mi][mu][dv];
 
    if(ps) ans = min(ans, minV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = min(ans, minV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = min(ans, minV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = minV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) { 
            tmp *= -1;
            tmp /= a[n];
            tmp *= -1;
        }
        else
            tmp /= a[n];
        ans = min(ans, tmp);
    }
    return e[n][ps][mi][mu][dv] = ans;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<4; i++)
        scanf("%d", op+i);
 
    for(int i=0; i<15; i++)
        for(int j=0; j<15; j++)
            for(int k=0; k<15; k++)
                for(int l=0; l<15; l++)
                    for(int m=0; m<15; m++)
                        d[i][j][k][l][m] = e[i][j][k][l][m] = INF+1;
 
    printf("%d\n", maxV(n, op[0], op[1], op[2], op[3]));
    printf("%d\n", minV(n, op[0], op[1], op[2], op[3]));
    return 0;
}
 
cs


>> 맨처음 풀이에 대해 잘못된 점을 파악한 다음(나눗셈에 대한 처리), 코드를 수정하니 AC 를 받았다.

>> 근데 다시생각해보면 왜 DP 로 가능한지 모르겠다...



< 마지막 테케가 안나오는 소스코드 >


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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
 
int a[15], op[4];
int d[15][15][15][15][15];
int e[15][15][15][15][15];
const int INF=1e9;
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int min(int a, int b)
{
    return a < b ? a : b;
}   
 
int maxV(int n, int ps, int mi, int mu, int dv)
{
    int ans = -INF;
    if(n == 1) return a[n];
    if(d[n][ps][mi][mu][dv]!=INF+1) return d[n][ps][mi][mu][dv];
 
    if(ps) ans = max(ans, maxV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = max(ans, maxV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = max(ans, maxV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = maxV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) tmp *= -1;
        tmp /= a[n];
        tmp *= -1;
        ans = max(ans, tmp);
    }
    return d[n][ps][mi][mu][dv] = ans;
}
 
int minV(int n, int ps, int mi, int mu, int dv)
{
    int ans = INF;
    if(n == 1) return a[n];
    if(e[n][ps][mi][mu][dv]!=INF+1) return e[n][ps][mi][mu][dv];
 
    if(ps) ans = min(ans, minV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = min(ans, minV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = min(ans, minV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = minV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) tmp *= -1;
        tmp /= a[n];
        tmp *= -1;
        ans = min(ans, tmp);
    }
    return e[n][ps][mi][mu][dv] = ans;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<4; i++)
        scanf("%d", op+i);
 
    for(int i=0; i<15; i++)
        for(int j=0; j<15; j++)
            for(int k=0; k<15; k++)
                for(int l=0; l<15; l++)
                    for(int m=0; m<15; m++)
                        d[i][j][k][l][m] = e[i][j][k][l][m] = INF+1;
 
    printf("%d\n", maxV(n, op[0], op[1], op[2], op[3]));
    printf("%d\n", minV(n, op[0], op[1], op[2], op[3]));
    return 0;
}
cs


>> 마지막 테케의 최소값이 -36이 나온다..... -24 라는데...ㅜ

>> 가만 생각해보니 DP 가 아닌 것 같다. 모든 경우의 수를 생각해서 풀면 될 것 같은 생각이 든다. (brute force)

>> 나눗셈에 대한 처리를 잘못했다.

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

[14890] 경사로  (0) 2018.03.06
[14889] 스타트와 링크  (0) 2018.02.28

[10942] 팰린드롬?

BOJ/DP2018. 2. 22. 23:49

http://boj.kr/10942


DP - basic


d[i][j] = i~j 까지가 팰린드롬인지.


< 소스코드 >


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>
#include <string.h>
 
int p[2001];
int d[2001][2001];
 
int isP(int s, int e)
{
    int i;
    if(s >= e) return 1;
    if(d[s][e] != -1) return d[s][e];
    if(p[s] != p[e]) return 0;
    return d[s][e] = isP(s+1, e-1);
}
 
int main()
{
    int i, j, n, m;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++)
        scanf("%d", p+i);
 
    memset(d, -1, sizeof(d));
 
    scanf("%d", &m);
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", isP(a, b));
    }
 
    return 0;
}
cs


>> 모든 경우를 다 구해놓고 하려다가 시간만 쓰고, 머리만 쓴거 같다.

>> 쿼리마다 필요한걸 구하면서 그때 구한걸 저장해(메모이제이션) 놓으면 된다..



< 바텀업 >


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 <cstdio>
int n;
int a[2000];
bool d[2000][2000];
int main() {
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    for (int i=0; i<n; i++) {
        d[i][i] = true;
    }
    for (int i=0; i<n-1; i++) {
        if (a[i] == a[i+1]) {
            d[i][i+1] = true;
        }
    }
    for (int k=3; k<=n; k++) {
        for (int i=0; i<=n-k; i++) {
            int j = i+k-1;
            if (a[i] == a[j] && d[i+1][j-1]) {
                d[i][j] = true;
            }
        }
    }
    int m;
    scanf("%d",&m);
    while (m--) {
        int s, e;
        scanf("%d %d",&s,&e);
        printf("%d\n",d[s-1][e-1]);
    }
    return 0;
}
cs


>> 과거 AC 받은 코드인데, 백준님 코드 같다.. 내스타일의 코드는 아니므로...


>> 길이가 1인 부분수열은 반드시 팰린드롬이다.

>> 길이가 2인 부분수열은 두 수가 같을때만 팰린드롬이다.

>> d[i][j] 가 팰린드롬이려면 a[i] == a[j] 이고 d[i+1][j-1] 이 팰린드롬이여야 한다.

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

[9251] LCS  (0) 2018.04.21
[14002] 가장 긴 증가하는 부분 수열 4  (0) 2018.04.18
[1890] 점프  (0) 2018.02.22
[2216] 문자열과 점수  (0) 2018.02.21
[11048] 이동하기  (0) 2018.02.18

[1890] 점프

BOJ/DP2018. 2. 22. 22:05

http://boj.kr/1890


DP - basic


D[i][j] : (1, 1)에서 (i, j) 까지 오는 방법의 수


< 소스코드 >


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
#include <stdio.h>
 
int n;
int g[101][101];
long long d[101][101];
 
long long jump(int r, int c)
{
    int k = g[r][c];
    long long ret = 0;
    if(r == n && c == n) return 1;
    if(r > n || c > n || k == 0) return 0;
    if(d[r][c] != -1) return d[r][c];
 
    ret += jump(r+k, c);
    ret += jump(r, c+k);
    return d[r][c] = ret;
}
 
 
int main()
{
    int i, j;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++) {
        for(j=1; j<=n; j++) {
            scanf("%d", &g[i][j]);
            d[i][j] = 1LL*(-1);
        }
    }
    printf("%lld\n", jump(1, 1));
    return 0;
}
 
cs


>> 10 : ret 를 int 로 선언해서 81%에서 틀렸었다....



< 과거 소스코드 >


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


>> 역시 재귀로 풀었지만, go(n, n) 으로 시작해서 불필요하게 머리를 더 쓴거 같다..

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

[14002] 가장 긴 증가하는 부분 수열 4  (0) 2018.04.18
[10942] 팰린드롬?  (0) 2018.02.22
[2216] 문자열과 점수  (0) 2018.02.21
[11048] 이동하기  (0) 2018.02.18
[9184] 신나는 함수 실행  (0) 2018.02.16

[2216] 문자열과 점수

BOJ/DP2018. 2. 21. 08:15

http://boj.kr/2216


d[i][j] = s의 i번째 문자열까지, t의 j번째 문자열까지의 최대 점수


< AC 코드 >


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
#include <stdio.h>
#include <string.h>
#define mINF 0x80000000
 
int a, b, c;
int slen, tlen;
char s[3005], t[3005];
int d[3005][3005];
 
int max(int x, int y)
{
    return x > y ? x : y;
}
 
int go(int si, int ti)
{
    int ret = mINF;
    if(d[si][ti]!=mINF) return d[si][ti];
 
    if(si == slen) return b * (tlen-ti);
    if(ti == tlen) return b * (slen-si);
 
    if(s[si] == t[ti])
        ret = max(ret, go(si+1, ti+1)+a);
    if(s[si] != t[ti])
        ret = max(ret, go(si+1, ti+1)+c);
    ret = max(ret, go(si+1, ti)+b);
    ret = max(ret, go(si, ti+1)+b);
    return d[si][ti] = ret; 
}
 
int main()
{
    int i, j;
    scanf("%d%d%d%s%s", &a, &b, &c, s, t);
    slen = strlen(s);
    tlen = strlen(t);
    for(i=0; i<3005; i++) for(j=0; j<3005; j++) d[i][j] = mINF;
    printf("%d\n", go(0, 0)); 
    return 0;
}
 
cs


>> 0x8000000 : int 의 최소값이다.

>> 무조건 위에서 아래로 가도록 짜진 말아야겠다...



< 틀린 코드 >


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
#include <stdio.h>
#include <string.h>
#define mINF 0x80000000
 
int a, b, c;
char s[3005], t[3005];
int d[3005][3005];
 
int max(int x, int y)
{
    return x > y ? x : y;
}
 
int go(int si, int ti)
{
    int ret = mINF;
    if(si < 0) return b * (ti-1); 
    if(ti < 0) return b * (si-1);
    if(d[si][ti]!=mINF) return d[si][ti];
 
    if(s[si] == t[ti])
        ret = max(ret, go(si-1, ti-1)+a);
    if(s[si] != t[ti])
        ret = max(ret, go(si-1, ti-1)+c);
    ret = max(ret, go(si-1, ti)+b);
    ret = max(ret, go(si, ti-1)+b);
    return d[si][ti] = ret; 
}
 
int main()
{
    int i, j;
    scanf("%d%d%d%s%s", &a, &b, &c, s, t);
    for(i=0; i<3005; i++) for(j=0; j<3005; j++) d[i][j] = mINF;
    printf("%d\n", go(strlen(s)-1, strlen(t))-1); 
    return 0;
}
 
cs


>> 점화식은 맞는데, 18%에서 틀렸다고 한다. 왜 틀린건지 모르겠다...ㅜㅜ

>> 17, 18 에서의 탈출조건도 ti+1, si+1 인거 같은데, 이렇게 하면 테케도 통과를 못한다...


>> 위 코드에 대한 반례


5 -3 -6 

a 

b


>> 정답코드에서는 -6이, 위 코드에서는 -4가 나온다...


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

[10942] 팰린드롬?  (0) 2018.02.22
[1890] 점프  (0) 2018.02.22
[11048] 이동하기  (0) 2018.02.18
[9184] 신나는 함수 실행  (0) 2018.02.16
[2302] 극장 좌석  (0) 2018.02.05

[11048] 이동하기

BOJ/DP2018. 2. 18. 01:24

http://boj.kr/11048


기본 DP2.


D[i][j] : (1, 1) 에서 (i, j)으로 이동하면서 가져올 수 있는 사탕의 최대 갯수


< 소스코드 >


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


>> go(n-1, m-1) 은 고려할 필요가 없다. 



< Bottom Up >


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


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

[1890] 점프  (0) 2018.02.22
[2216] 문자열과 점수  (0) 2018.02.21
[9184] 신나는 함수 실행  (0) 2018.02.16
[2302] 극장 좌석  (0) 2018.02.05
[1937] 욕심쟁이 판다  (0) 2018.02.01

티스토리툴바