글 읽기 - 자두나무 배열을 최적화 시키면 틀렸다 뜨네요 ...??

kkw564 6년 전 1

1000초 -> 배열 1001

이동위치 1또는2 -> 배열 3

이동 가짓수 30 -> 배열 31

= 틀렸습니다.(아마 런타임 에러인것같네요 아무데나 참조해서 틀렸다고 하는것같구요.)

[1003][3][33]으로 하면 AC인데

제가 무슨 헛생각을 하고있는걸까요..? 고수님들 도와주세요

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

// 초, 위치, 이동수 = 먹은 자두
int DP[1001][3][31];
// 초, 위치 = 자두 있으면 1 없으면 0
int jadu[1001][3];

int main()
{
	int T, W;
	scanf("%d %d", &T, &W);

	for (int i = 1; i <= T; i++)
	{
		int pos;
		scanf("%d", &pos);

		jadu[i][pos] = 1;
	}

	// 1초에 1번 위치이고 0번 움직일 때
	// 1초에 2번 위치이고 1번 움직일 때 
	// 자두가 있는곳은 자두를 먹는다.
	DP[1][1][0] = jadu[1][1];
	DP[1][2][1] = jadu[1][2];

	// T초동안 DP
	int ans = 0;
	for (int i = 2; i <= T; i++)
	{
		for (int k = 0; k <= W; k++)
		{			
			// i초에 1번 위치에 이동횟수 k로 있을때 DP는
			// i-1초에 1번위치에 그대로 가만히 있을 때 또는 2번위치에서 한칸 움직였을때의 최대
			DP[i][1][k] = max(DP[i - 1][1][k], DP[i - 1][2][k - 1]) + jadu[i][1];
			DP[i][2][k] = max(DP[i - 1][2][k], DP[i - 1][1][k - 1]) + jadu[i][2];

			ans = max(ans, DP[i][1][k]);
			ans = max(ans, DP[i][2][k]);
		}
	}
	
	printf("%d", ans);

	return 0;
}

cprayer 6년 전 2

k가 0부터 시작해서 DP 배열이 음수 첨자를 가지는 경우가 생기네요. 1부터 시작하면 되실 듯 합니다.

kkw564 6년 전 1

1003 3 33도 똑같이 음수인자가존재해도 통과하는데 이건왜이런건가요?

cprayer 6년 전 2

DP[i][2][-1]이 DP[i][1][30]을 참조하면 잘못된 값이 출력되고 DP[i][1][32]를 참조하면 0이므로 무시됩니다. 그래서 일부러 배열 크기를 넉넉하게 잡습니다.

kkw564 6년 전 0

아하 감사합니다 이해했습니다 !

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

문제

문제

출처

ICPC

자두나무 배열을 최적화 시키면 틀렸다 뜨네요 ...??

kkw564 6년 전 1

cprayer 6년 전 2

kkw564 6년 전 1

cprayer 6년 전 2

kkw564 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말