글 읽기 - 반례 하나 들어주시면 감사하겠습니다.

legendmic2 4년 전 0

dp를 이용해서 풀었습니다. 질문게시판에 있는 반례들은 모두 되더라구요..

제가 캐치하지 못한 부분이 있을 것 같아서 질문드립니다.

끝까지 읽어주셔서 감사합니다

#include <iostream>
#include <algorithm>

#define MAX 100000

long long sticker[MAX+1][2];
long long dp[MAX + 1][3];
// dp[i][j] : 2 x i 에서 얻을 수 있는 최대 점수
// i번 열에서 뜯는 스티커는 j
// dp[i][0] 뜯지않음
// dp[i][1] 위쪽 스티커를 뜯음
// dp[i][2] 아래쪽 스티커를 뜯음

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int t; cin >> t;
	int n;

	while (t--)
	{
		cin >> n;
		
		for (int i = 0; i < n; ++i)
		{
			cin >> sticker[i][0];
		}
		for (int i = 0; i < n; ++i)
		{
			cin >> sticker[i][1];
		}

		dp[0][0] = 0;
		dp[0][1] = sticker[0][0];
		dp[0][2] = sticker[0][1];

		for (int i = 1; i <= n; ++i)
		{
			dp[i][0] = max({ dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
			// i-1열에서 스티커를 어떻게 뜯었는지 상관이 없다
			dp[i][1] = max( dp[i - 1][0], dp[i - 1][2] ) + sticker[i][0];
			// i-1열에서 위쪽 스티커는 뜯으면 안 된다
			dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + sticker[i][1];
			// i-1열에서 아래쪽 스티커는 뜯으면 안 된다
		}

		cout << max({ dp[n][0], dp[n][1], dp[n][2] }) << "\n";
		
	}
	
}

legendmic2 4년 전 0

해결했습니다! dp[0][0] ~ dp[0][2]를 쓸데없이 초기화해주고있었고, sticker를 입력받을때 i=1부터 시작하게 바꿨더니 풀렸습니다

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

문제

문제

출처

ICPC

반례 하나 들어주시면 감사하겠습니다.

legendmic2 4년 전 0

legendmic2 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말