hwangtmdals   4달 전

제가 실수로 잘못된 코드를 작성해서 제출했는데 맞았습니다! 가 올라와서 당황했습니다.

#include <cstdio>

int tri[502][502];
int memo[502][502];

int main()
{
    int n;
    scanf("%d", &n);

    for(int i = 1; i<=n; i++)
    {
        for(int j = 1; j<i+1;j++)
        {
            scanf("%d",&tri[i][j]);
        }
    }

    for(int i = 1; i<=n; i++)
    {
        for(int j = 1; j<i+1;j++)
        {
            memo[i][j] = memo[i-1][j-1] + tri[i][j];
            if(memo[i][j]<memo[i-1][j] + tri[i][j])
            {
                memo[i][j] = memo[i-1][j] + tri[i][j];
            }
        }
    }

 int max = 0;

    for(int i = 0; i<n; i++)
    {
        if(max<memo[n][i])
        {
            max = memo[n][i];
        }
    }

    printf("%d\n", max);

    return 0;
}

볼드체로 표시된 부분이 잘못된 코드인데요,
어쩌면 최적해가 n,n칸에 저장되었을지도 모르는데 이 프로그램은 탐색하지 않습니다.

다행인지 아닌지는 잘 모르겠지만 채점 프로그램에 n,n에 최적해가 들어있는 경우가 없던 모양입니다.


만약 테스트 데이터가 

3

1

0 1

0 0 1

과 같은 방식으로 주어진다면 위의 프로그램은 3이 아닌 2의 값을 출력하게 됩니다.

이런 유형의 데이터 추가가 필요할 것 같습니다.




baekjoon   3달 전

추가했습니다.

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