글 읽기 - 2579번 반례 또는 틀린 이유 지적좀 부탁드립니다.

pianissimo 5년 전 0

게시판에 있는 반례들은 다 해봤는데 아직까지는 못찾았습니다.
a배열은 계단의 값이고 result는 dp결과 배열입니다.
알고리즘은 result[n]은
result[n-3] + a[n-2] + a[n], result[n-4] + a[n-2] + a[n], result[n-3] + a[n-1] + a[n]
중 최대값으로 했습니다. 이전의이동경우가 (1,2), (2,2), (2,1)인 경우입니다.
저 중 result[n-3]이 그 이전에 (2,1) 로 뛴 경우 그 다음은 (1,2)를 오를 수 없으므로 뒤의 두가지만 비교합니다.
예외케이스로 1~5까지의 result값은 그냥 구했습니다.
도움좀 부탁드립니다.

#include <stdio.h>
#include <stdlib.h>

int a[301] = {0};
int result[301] = {0};

int max(int idx1, int idx2, int idx3){
	if(idx1 >= idx2){
		if(idx1 >= idx3)
			return idx1;
		else
			return idx3;
	}
	else{
		if(idx2 >= idx3)
			return idx2;
		else
			return idx3;
	}
}

int main(void){
	int step;
	int i;
	scanf("%d",&step);
	for(i=1; i<=step; i++)
		scanf("%d",&a[i]);
	result[1] = a[1];
	result[2] = a[1] + a[2];
	result[3] = max(0, a[1] + a[3], a[2] + a[3]);
	result[4] = max(a[1]+a[2]+a[4], a[1]+a[3]+a[4], 0);
	result[5] = max(result[2]+a[4]+a[5], result[1]+a[3]+a[5], a[2]+a[3]+a[5]);
	for(i=6 ; i<=step; i++){
		if(result[i-3] == result[i-6] + a[i-4] + a[i-3]){
			result[i] = max(0, result[i-4]+a[i-2]+a[i],
			result[i-3] + a[i-1] + a[i]);
		}
		else{
			result[i] = max(result[i-3] + a[i-2] + a[i],
			result[i-3] + a[i-1] + a[i],
			result[i-4] + a[i-2] + a[i]);
		}
	}

	//for(i=1; i<=step; i++)
	printf("%d\n",result[step]);

}

doju 5년 전 1

아래 예시에서 result[3]은 3점이며, 이는 1번 - 3번 계단을 밟아도 가능하고 2번 - 3번 계단을 밟아도 가능합니다. 답은 1번 - 3번 - 4번 - 6번 계단을 밟고 6점을 얻는 것인데 지금 코드에서는 이 방법을 고려하지 못합니다.

pianissimo 5년 전 0

감사드립니다.!!

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

문제

문제

출처

ICPC

2579번 반례 또는 틀린 이유 지적좀 부탁드립니다.

pianissimo 5년 전 0

doju 5년 전 1

pianissimo 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말