글 읽기 - 스티커 dp 문제 왜 테스트 케이스마다 dp 배열을 초기화해야 하나요?

cmyell74 6년 전 0

for (int i = 0; i < 2; i++)
for (int j = 0; j < n; j++)

dp[i][j] = 0;

이걸 코드의 마지막에 넣지 않았더니 9%에서 틀렸다가 나오고

넣었더니 맞았습니다.

그런데 정말 의아한게, 어차피 스티커의 맨 앞 column부터 시작해서 차례차례 구해주는 것인데 왜 다시 초기화가 필요한지 궁금합니다.

코드 첨부합니다. 고수님들 도와주세요!!ㅠㅠㅠㅠ

#include <algorithm>
#pragma warning (disable:4996)
using namespace std;
int arr[2][100001];
int dp[2][100001];

int main() {
	int T, n;
	scanf("%d", &T);
	for (int kk = 0; kk < T; kk++) {
		scanf("%d", &n);
		for (int i = 0; i < 2; i++) 
			for (int j = 0; j < n; j++) 
				scanf("%d", &arr[i][j]);

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 2; j++) {
				if (i == 0) {
					dp[j][i] = arr[j][i]; continue;
				}
				if (i == 1) {
					dp[j][i] = dp[1 - j][i - 1] + arr[j][i];
					continue;
				}
				dp[j][i] = max(dp[1 - j][i - 1], dp[1 - j][i - 2]) + arr[j][i];
			}
		}

		printf("%d\n", max(dp[0][n - 1], dp[1][n - 1]));

		for (int i = 0; i < 2; i++)
			for (int j = 0; j < n; j++)
				dp[i][j] = 0;

	}
}

cmyell74 6년 전 0

헉 그렇군요 ㅠㅠ 그거일줄은 생각도 못했어요

정말 감사합니다 ♡♡

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

문제

문제

출처

ICPC

스티커 dp 문제 왜 테스트 케이스마다 dp 배열을 초기화해야 하나요?

cmyell74 6년 전 0

cmyell74 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말