제가 실수로 잘못된 코드를 작성해서 제출했는데 맞았습니다! 가 올라와서 당황했습니다.
#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의 값을 출력하게 됩니다.
이런 유형의 데이터 추가가 필요할 것 같습니다.
추가했습니다.
댓글을 작성하려면 로그인해야 합니다.
hwangtmdals 7년 전
제가 실수로 잘못된 코드를 작성해서 제출했는데 맞았습니다! 가 올라와서 당황했습니다.
#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의 값을 출력하게 됩니다.
이런 유형의 데이터 추가가 필요할 것 같습니다.