글 읽기 - 포도주시식 반례를 모르겠습니다 ㅠㅠ

jh1125kr 7년 전 0

질문글에 나온 테스트케이스는 다 해봤는데..어디서 틀렸는지 모르겠습니다..ㅠㅠ

1 2 3 4 5 6 7
       #   # #
      #      # #
         # # #
      #   # #
   # #        #
      ##        #

dp[i][1] = max(dp[i - 1][2], dp[i - 1][3]) + grape[i];
dp[i][2] = max(dp[i - 2][1], dp[i - 2][2]) + grape[i];
dp[i][3] = max(dp[i - 3][1], dp[i - 3][2]) + grape[i];
이렇게 경우를 따졌습니다ㅠㅠ

그리고 이미 다른 방식으로는 풀었긴했는데.. 이방식으로는 왜 안되는지.. 몰라서 질문합니다..ㅠㅠ

#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int grape[10005]; //10002
int dp[10005][4];

int main()
{
	
		for (int i = 0; i < 10005; i++)
		{
			grape[i] = 0;
			for (int j = 0; j < 4; j++)
			{
				dp[i][j] = 0;
			}
		}
		int mx = -1;
		int n;
		cin >> n;
		for (int i = 2; i < n + 2; i++)
		{
			scanf("%d", &grape[i]);
		}
		for (int i = 2; i < n + 2; i++)
		{
			dp[i][1] = max(dp[i - 1][2], dp[i - 1][3]) + grape[i];
			dp[i][2] = max(dp[i - 2][1], dp[i - 2][2]) + grape[i];
			dp[i][3] = max(dp[i - 3][1], dp[i - 3][2]) + grape[i];
		}
		for (int i = n; i < n + 2; i++)
		{
			for (int j = 1; j <= 3; j++)
			{
				if (mx < dp[i][j]) mx = dp[i][j];
			}
		}
		cout << mx << endl;
	
}

yukariko 7년 전 1

자세히는 보지 않았지만 i = 2 일때 i - 3을 접근하여 오버플로우가 발생할 수 있습니다.

jh1125kr 7년 전 0

yukariko

헐...ㅜㅜ고치니까 맞았네요..뭐때문에 그런지몰라서 계속 답답했는데 ㅠㅠ
감사합니다.....하ㅠㅠ

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

문제

문제

출처

ICPC

포도주시식 반례를 모르겠습니다 ㅠㅠ

jh1125kr 7년 전 0

yukariko 7년 전 1

jh1125kr 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말