글 읽기 - 제 경우는 어떤 것이 틀렸을까요?ㅠㅠ

goodksj 5년 전 0

dp[idx][num]

에서 num이 1이면 연속해서 선택가능하다.

num이 0이면 연속해서 선택불가능하다.

따라서 dp[idx][1] = max(dp[idx+1][0], dp[idx+2][1]) + wine[idx]

dp[idx][0] = dp[idx+2][1] + wine[idx]

라는 점화식을 세웠는데 어디서 잘못될걸까요?ㅠㅠ 고수님들 답변부탁드립니다!

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
int n;
int wine[100001];
int dp[100001][2];
int solve(int idx, int cont){
	if(idx >= n) return 0;

	int& ret = dp[idx][cont];

	if(ret != -1) return ret;

	ret = 0;

	if(cont == 1){
		ret = max(solve(idx + 1, 0), solve(idx + 2, 1));
	}
	else{
		ret = solve(idx + 2, 1);
	}
	return ret += wine[idx];
}

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

	memset(dp, -1, sizeof(dp));

	for(int i = 0; i < n; i++){
		scanf("%d", &wine[i]);
	}
	int ret = 0;

	int	ret1 = solve(0,1);
	int ret2 = solve(1,1);
	ret = max(ret1, ret2);

	printf("%d\n", ret);

	return 0;
}

goodksj 5년 전 0

아 선택을 안하고 넘어가도 되는 군요.

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

문제

문제

출처

ICPC

제 경우는 어떤 것이 틀렸을까요?ㅠㅠ

goodksj 5년 전 0

goodksj 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말