글 읽기 - 반례 주시면 감사하겠습니다.

huh0918 2년 전 0

d[n][YES] : N 번째 계단 밟을 때 최대값

d[n][NP] : N 번째 계단 안밟을 때 최대값입니다.

제가 세운 점화식입니다.

d[n][yes] :
d[n-1][NO] + An OR d[n-2][no]+An-1+An

d[n][no] :
d[n-1][yes] OR d[n-1][no]

어느 부분이 틀렸을련지.. 도와주시면 감사하겠습니다.

#include <stdio.h>
#define MAX_N 300 
#define YES 1
#define NO 0
#define MAX(a,b) ((a)>(b))?(a):(b)

int n, arr[MAX_N+1], d[MAX_N+1][2];

int main()
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++) { scanf("%d", &arr[i]); }
	
	d[1][YES] = arr[1]        ; d[1][NO] = 0;
	d[2][YES] = arr[1]+arr[2] ; d[2][NO] = arr[1];
	for (int i=3; i<=n; i++)
	{
		d[i][YES] = MAX (   d[i-1][NO] + arr[i] , 
						d[i-2][NO] + arr[i-1] + arr[i] );
		d[i][NO] = MAX( d[i-1][YES], d[i-1][NO] );
	}

	printf("%d\n", d[n][YES] );
	return 0;
}

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

문제

문제

출처

ICPC

반례 주시면 감사하겠습니다.

huh0918 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말