글 읽기 - 숫자삼각형 DP 질문이요!

youu 6년 전 0

d[i][j]는 i행j열의 숫자까지 합했을 때의 최대 값이라고 가정하고 점화식을 세웠습니다.

d[i][j] = max(d[i - 1][j - 1] + a[i][j], d[i - 1][j + 1] + a[i][j]); (배열a는 scanf입력받은 값입니다.)

제가 보기에는 점화식이 맞는 것 같은데 예제조차도 틀리네요

혹시 어디가 틀렸는지 간단하게라도 짚어주실 분 계신가요ㅠㅠㅠ

#include <stdio.h>
#define max(a,b) a>b?a:b 
int a[501][501];
int d[501][501];
int main() {
	int t;
	scanf("%d", &t);
	for(int i =1 ; i <= t; ++i)
		for (int j = 1; j <= i; ++j) 
			scanf("%d", &a[i][j]);
    
	d[1][1] = a[1][1];
	for (int i = 2; i <=t; ++i) 
		for (int j = 1; j <= i; ++j) 
			d[i][j] = max(d[i - 1][j - 1] + a[i][j], d[i - 1][j + 1] + a[i][j]);
    
	int sum = 0;
	for (int i = 1; i < t; i++) 
		sum = max(sum, d[t][i]);
    
	printf("%d\n", sum);
	return 0;
}

jinsj1 6년 전 1

점화식 접근은 잘 하셨습니다.

하지만, d[i-1][j-1] 과 d[i-1][j] 가 현재 위치에서 인접한 숫자가 됩니다.

또한, 정답을 출력하는 과정에서도, d[t][t] 도 확인을 해주셔야합니다.

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

문제

문제

출처

ICPC

숫자삼각형 DP 질문이요!

youu 6년 전 0

jinsj1 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말