글 읽기 - 2579 계단오르기 문제 질문입니다.

ljy8947 8년 전 1

동적 프로그래밍을 공부하기 위해서 풀어보았습니다.

예제와 정답이 동일하게 나오는데 8차례 정도 코드를 고쳐보아도 계속 틀렸습니다가 나와서 질문드립니다.

트리 형태로 깊이우선 탐색기법을 이용해서 구현해

#include <stdio.h>

#define NUMBER_OF_STEPS 301 // 계단의 수
#define MAX_SCORE 10001 // 계단 점수의 최대 값.
#define VISITED 1 // 방문 플레그.
#define UNVISITED 0 // 비 방문 플레그
#define NUMBER_OF_CASE 1000 // 경우의 수.

void Get_Max_Score(int, int*, int*, int (*)[2]);

int main ()
{
    int i, j=0, N, C=0, MAX=0;
    int sum[NUMBER_OF_CASE]={};  // 각 케이스의 결과를 저장.
    int Score[NUMBER_OF_STEPS][2]={}; // [n][0] n단계의 값을 저장. [n][1] n단계 방문 여부 저장.

    scanf("%d", &N);
    //if(N<1 || N>NUMBER_OF_STEPS) exit(1);

    for(i=0; i<N; i++) //계단의 점수를 입력
    {
        scanf("%d", &Score[i][0]);
        //if(Score[i][0]<1 || Score[i][0]>MAX_SCORE) exit(1);
    }

    for(C=0; C<NUMBER_OF_CASE; C++) sum[C]=Score[N-1][0]; // 모든 경우 N번째 점수가 입력되어야 함
    Score[N-1][1]= VISITED; //모든 경우 N 단계를 방문해야 함.
    C=0;
    MAX=Score[N-1][0];

    Get_Max_Score(N-2, sum, &C, Score); //왼쪽 자식 방문
    C++;
    Get_Max_Score(N-3, sum, &C, Score); //오른쪽 자식 방문

    for(j=0; j<NUMBER_OF_CASE; j++) if(sum[j]>MAX) MAX= sum[j]; // 가장 긴 루트를 (가장 큰 점수를) MAX에 저장

    printf("%d", MAX);

    return 0;
}

void Get_Max_Score(int n, int* sum, int* C, int (*Score)[2])  //변수 C는 sum의 인덱스로, 다른 루트를 선택할 경우 index를 증가시켜 구분해줌. 
{
    if(Score[n+1][1]==VISITED) // 부모 노드를 방문 했을 경우.
    {
        sum[*C]+= Score[n][0];
        Score[n][1]= VISITED;
        if(n<=1)
        {
            sum[++(*C)]= sum[--(*C)]-Score[n][0]; //부모노드로 다시 되돌아가면서 방문했던 노드의 점수를 빼줘야 함. (다른 루트를 선택하기 위해)
            (*C)++;
            Score[n][1]= UNVISITED;
            return;
        }
        Get_Max_Score(n-2, sum, C, Score); //부모노드 방문했을 경우, 무조껀 손자 노드만 방문 가능 (연속된 3개의 숫자 방문 불가 조건에 의해)
        Score[n][1]= UNVISITED;
        if(Score[n+1][1]==VISITED)
        {
            sum[++(*C)]= sum[--(*C)]-Score[n][0];  
            (*C)++;
        }
    }
    else
    {
        sum[*C]+= Score[n][0];
        Score[n][1]= VISITED;
        if(n==0)
        {
            sum[++(*C)]= sum[--(*C)]-Score[n][0];
            (*C)++;
            Score[n][1]= UNVISITED;
            return;
        }
        Get_Max_Score(n-1, sum, C, Score);
        Score[n][1]= UNVISITED;
        if(Score[n+1][1]==VISITED)
        {
            sum[++(*C)]= sum[--(*C)]-Score[n][0];
            (*C)++;
        }
        if(n<=1)
        {
            sum[++(*C)]= sum[--(*C)]-Score[n][0];
            (*C)++;
            Score[n][1]= UNVISITED;
            return;
        }
        Get_Max_Score(n-2, sum, C, Score);
        Score[n][1]= UNVISITED;
        if(Score[n+1][1]==VISITED)
        {
            sum[++(*C)]= sum[--(*C)]-Score[n][0];
            (*C)++;
        }
    }
}

hananakajima 8년 전 5

2차원배열쓰실 필요없으시고 쉽게 생각하심됩니다.

n번째 계단을 밟는 다면 2가지 밖에없죠. n번째 밟고 -> n-2번째 계단밟는경우, n번째 n-1번째 밟고 n-3번째 밟는 경우.

처음에 씨앗으로 계단 2층까지만 최대값 넣어주고 나머지 배열로 채워넣으면 간단히 풀립니다.

비슷한문제로 포도주,스티커 문제도있습니다. 이거 푸시고나면 쉽게 푸실듯.

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

문제

문제

출처

ICPC

2579 계단오르기 문제 질문입니다.

ljy8947 8년 전 1

hananakajima 8년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말