안녕하세요

다름이 아니라 아래 문제 다이나믹 프로그래밍 두문제를 풀다 막혀서 몇주 고민하다하다 조언을 구하고자 글 남깁니다.

https://www.acmicpc.net/problem/1514< = 풀이 방법 DP. 최대 3개의 디스크까지 동시 회전이 가능하므로 DP[c][n1][n2] : c는 현재 확인해야 될 디스크 위치. n1은 현재 디스크의 숫자. n2는 다음 디스크의 숫자. 로 DP를 구현했습니다.

https://www.acmicpc.net/problem/2394< = 기본적으로 KOI 2008 공주구하기와 유사한 방법으로 접근하였습니다. DP[a][b] N으로 가는 위치가 a이고 N에서 1로 다시 오는 위치가 b에 있을때의 경우의 수중 방문하는 node가 가장 많은 경우를 return하게 했습니다. 그런데 어느 부분이 잘못된 것인지 막막한 상태라 조언을 구하게 되었습니다.

알려주시면 감사하겠습니다.

include

define INF 0x7fffff

define MAXN 260

int N; int idx1, idx2; int path1[MAXN]; int path2[MAXN]; int map[MAXN][MAXN]; int memo[MAXN][MAXN];

int max(int a, int b) { if (a > b) return a; else return b; }

int calc(int a, int b, int k) { int ret;

if (k == N) {
    if (map[a][N] && map[b][N])
        return memo[a][b] = 1;
    else
        return -INF;
}

if (memo[a][b] != -1)
    return memo[a][b];

memo[a][b] = calc(a, b, k + 1);
if (map[a][k]) {
    ret = calc(k, b, k + 1) + 1;
    memo[a][b] = max(ret, memo[a][b]);      
}

if (map[b][k]) {
    ret = calc(a, k, k + 1) + 1;
    memo[a][b] = max(ret, memo[a][b]);
}

return memo[a][b];

}

void init() { int i, j; idx1 = idx2 = 0; for (i = 0; i <= N; i++) for (j = 0; j <= N; j++) memo[i][j] = -1, map[i][j] = 0; path1[0] = 1; path2[0] = 1; path1[++idx1] = N; }

void find_path(int a, int b) { int i, mx_a, mx_b, nexta, nextb;

if (a == N || b == N)
    return;

mx_a = -INF; mx_b = -INF;
for (i = a + 1; i <= N; i++) {
    if (map[a][i] && i != b && memo[i][b] > mx_a) {
        mx_a = memo[i][b];
        nexta = i;
    }
}

for (i = b + 1; i <= N; i++) {
    if (map[b][i] && i != a && memo[a][i] > mx_b) {
        mx_b = memo[a][i];
        nextb = i;
    }
}

if (mx_a > 0 || mx_b > 0) {
    if (mx_a > mx_b) {
        path1[++idx1] = nexta;
        find_path(nexta, b);
    }
    else {
        path2[++idx2] = nextb;
        find_path(a, nextb);
    }
}

}

void swap(int a, int b) { int temp; temp = a; a = b; b = temp; }

void sort() { int i, j; for (i = 0; i < idx1; i++) for (j = i + 1; j <= idx1; j++) { if (path1[i] > path1[j]) swap(&path1[i], &path1[j]); } for (i = 0; i < idx2; i++) for (j = i + 1; j <= idx2; j++) { if (path2[i] < path2[j]) swap(&path2[i], &path2[j]); } }

void print_memo() { int i, j; for (i = 1; i <= N; i++) { for (j = 1; j <= N; j++) { printf("%13d", memo[i][j]); } printf("\n"); } }

int main() { int i, j, ret, p, q, mx, tmp_idx;

freopen("sample_input.txt", "r", stdin);
freopen("sample_output.txt", "w", stdout);

scanf("%d", &N);
init();
do {
    scanf(" %d %d", &p, &q);
    map[p][q] = 1;
    map[q][p] = 1;
} while (p && q);

ret = calc(1, 1, 2);    

//print_memo();
if (ret <= 0) {
    printf("0\n");
}
else if (ret == 1) {
    printf("2\n1 %d 1\n", N);
}
else {
    find_path(1, 1);
    printf("%d\n", ret + 1);
    sort();
    for (i = 0; i <= idx1; i++)
        printf("%d ", path1[i]);
    for (i = 0; i <= idx2; i++)
        printf("%d ", path2[i]);
    printf("\n");
}
//printf("%d %d\n", idx1, idx2);
return 0;

}