글 읽기 - 포도주시식 반례가 어떤게 있을까요?

cardbt 6년 전 0

일단, 기본적으로 계단오르기와 유사하게 작성했습니다.

계단오르기처럼 순서대로 진행해야된다는 규칙이 없긴합니다만, 결과적으로는 동일하다고 생각했습니다.

단, 4, 5, 1, 1, 10, 11 과 같을 경우에는 1은 마시지 않는것이 최대값이 되므로 이걸 응용해서 DP를 작성해봤습니다.

기본적으로는 순서대로 마시되 앞서 마신값의 최대값을 이용하는 방식이고, 세잔을 초과하는 앞 예를 들어 4, 5, 1, 1, 1, 10, 11 이라고해서 1을 모두 넘어갈 필요가 없으므로 최대 세잔 앞에 있는 포도주까지 고려해서 DP를 작성했습니다.

DP로직 자체는 계단오르기와 동일합니다.

예제와 게시판에 올려진 반례를 보두 돌려보고, 이것저것 반례를 돌려봐서 다 맞게 나왔는데, 제출하면 틀렸습니다가 나오네요.

반례가 어떤게 있을까요?

#include <stdio.h>

//2156
#define MAX(A, B) (A > B ? A : B)

int main()
{
	int arr[10001];
	int N, i;
	long total[10001][3]; // 0은 세칸 앞에서 왔을경우, 1은 두칸 앞에서 왔을경우, 2는 한칸 앞에서 왔을 경우

	scanf("%d", &N);

	memset(arr, 0, sizeof(arr));
	memset(total, 0, sizeof(total));

	for (i = 1; i <= N; i++)
	{
		scanf("%d", &arr[i]);
	}

	total[1][0] = arr[1];
	total[1][1] = arr[1];
	total[1][2] = arr[1];
	total[2][0] = arr[2];
	total[2][1] = arr[2];
	total[2][2] = arr[1] + arr[2];
	if (N >= 3)
	{
		total[3][0] = arr[3];
		total[3][1] = MAX(MAX(total[1][0], total[1][1]), total[1][2]) + arr[3];
		total[3][2] = MAX(total[2][0], total[2][1]) + arr[3];
	}

	for (i = 4; i <= N; i++)
	{
		total[i][0] = MAX(MAX(total[i-3][0], total[i-3][1]), total[i-3][2]) + arr[i];
		total[i][1] = MAX(MAX(total[i-2][0], total[i-2][1]), total[i-2][2]) + arr[i];
		total[i][2] = MAX(total[i-1][0], total[i-1][1]) + arr[i];
	}

	printf("%ld", MAX(MAX(total[N][0], total[N][1]), total[N][2]));

	return 0;
}

chojl1125 6년 전 3

3 2 1

계단오르기는 마지막 계단을 반드시 밟아야 하지만 포도주는 마지막 잔을 마시지 않을수도 있다는게 차이겠네요.

cardbt 6년 전 0

아! 아무 생각없이 마지막 값으로 최대값을 구하고 있었군요...

꼭 마지막일 필요 없다고 알고 있었는데 계단오르기 변형만 생각하다가 무심결에 마지막 값만 보고 있었네요 ㅠㅠ

감사합니다!

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

문제

문제

출처

ICPC

포도주시식 반례가 어떤게 있을까요?

cardbt 6년 전 0

chojl1125 6년 전 3

cardbt 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말