글 읽기 - 알고리즘에 잘못된 부분이 있을까요?

pokmk2 5년 전 0

dp에 위의 스티커를 선택했을 경우[0],

이전회차에서 선택하지 않은 경우와 이전 회차에서 아래를 선택한 경우를 비교해서 현재 회차의 위의 숫자를 더하게 하였고

아래의 스티커를 선택했을 경우[1],

이전회차에서 선택하지 않은 경우와 이전 회차에서 위를 선택한 경우를 비교해서 현재 회차의 아래의 숫자를 더하게 하였으며

선택하지 않았을 경우[2],

이전회차의 위 숫자와 아래 숫자를 선택한 경우 중 큰 숫자를 저장하도록 했는데요

질문게시판의 예시들은 다 확인해 보았는데 어느 부분이 잘못된 것인지 잘 모르겠습니다.

#include <iostream>

using namespace std;

long long int dp[100001][3]; // 위/아래/선택하지 않음
int suggesteddata[100001][2];

int max(int a, int b)
{
	if (a > b)return a;
	return b;
}

int main()
{
	std::ios_base::sync_with_stdio(false);	
	int num1, num2;
	cin >> num1;
	for (int f = 0; f < num1; ++f)
	{
		cin >> num2;
		dp[0][0] = dp[0][1] = dp[0][2] = 0;
		for (int i = 1; i <= num2; ++i)
		{
			cin >> suggesteddata[i][0];
		}
		for (int i = 1; i <= num2; ++i)
		{
			cin >> suggesteddata[i][1];
		}
		for (int i = 1; i <= num2; ++i)
		{
			dp[i][0] = max(dp[i - 1][1] , dp[i - 1][2])+ suggesteddata[i][0];	
            //전회의 선택하지 않음 + 현재 위치의 위 vs 전회의 아래 + 현재 위치의 위 
			dp[i][1] = max(dp[i - 1][0] , dp[i - 1][2] )+ suggesteddata[i][1];	
            //전회의 선택하지 않음 + 현재 위치의 아래 vs전회의 위 + 현재 위치의 아래
			dp[i][2] = dp[i - 1][0] > dp[i - 1][1] ? dp[i - 1][0] : dp[i - 1][1];	
            //선택하지 않았을 경우 전회의 보다 큰 숫자를 선택함
		}
		cout << max(max(dp[num2][0], dp[num2][1]), dp[num2][2]);
	}
}

seico75 5년 전 1

잘 작성하신 것 같습니다.

마지막 개행문자 출력만 넣으면 되겠네요.

pokmk2 5년 전 0

답변 감사합니다.

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

문제

문제

출처

ICPC

알고리즘에 잘못된 부분이 있을까요?

pokmk2 5년 전 0

seico75 5년 전 1

pokmk2 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말