hbh1107   5달 전

안녕하세요

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

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;

}

zlzmsrhak   5달 전

답장해주는 사람을 배려해주시면 안될까요..

다른 사람 코드가 읽기 매우 힘든데 다른 부분까지 난잡하면 답장 받기 어려울 것 같습니다.


먼저 글 하나에 문제가 2개라서 매우 헷갈리고,

아래 코드는 # 몇개가 빠져서 복붙으로 컴파일이 안되는데다가

코드에 박스가 이상하게 쳐져있어서 보기도 힘듭니다.


다른 분들의 질문글 읽어보시고 읽는 사람 편하게 다시 작성하시면 성실하게 답변해드리겠습니다.

hbh1107   5달 전

글쓴 제가 봐도 알아보기 힘드네요

정리해서 다시 올리겠습니다.  도움 주시면 감사하겠습니다

확인 감사합니다^^

댓글을 작성하려면 로그인해야 합니다.