글 읽기 - 2156 문제 질문입니다.

chatterboy 9년 전 0

안녕하세요.

현재 단계 k, 연속으로 먹은 잔의 수 cont라 하고 문제를 풀었습니다.

이 문제를 계단 오르기와 유사하게 코드를 구현했는데 틀리네요. (계단 오르기도 틀려서 다르게

했습니다 ㅋㅋ)

이 두 문제에서 제가 이렇게 해결하려고 했을 때 결정적으로 놓치는게 있는거 같아서 질문합니

다. ㅜㅜ

#include<stdio.h>
#include<string.h>

#include<algorithm>
using namespace std;

int n, wine[10001], dp[10001][3];

int f(int k, int cont){
	if(k > n)return 0;
	if(k == n)return wine[n];

	if(dp[k][cont] != -1)return dp[k][cont];

	dp[k][cont] = wine[k];
	if(cont == 1)dp[k][cont] += max(f(k+1, cont+1), f(k+2, 1));
	else dp[k][cont] += f(k+2, 1);

	return dp[k][cont];
}
void solve(){
	int i, j, ans;

	scanf("%d", &n);
	for(i = 1; i <= n; i++)scanf("%d", &wine[i]);

	for(i = 1; i <= n; i++)
		for(j = 1; j <= 2; j++)
			dp[i][j] = -1;

	ans = f(1, 1);
	for(i = 2; i <= n; i++)
		ans = max(ans, f(i, 1));

	printf("%d", ans);
}
int main(){
	solve();
}

movie_jo 9년 전 1

DP를 하실 때

dp[ i ][ j ]를 i 번째 와인을 j 번째로 마시고 있을 때의 (0이면 i 번째 와인을 마시지 않을 때) 최대값을 찾아보세요

일단 j == 0 일 때는 고려를 안하신것 같아요

ooxoxooxo 이런 패턴만 고려한다고 해야하나..?

oxxooxxoo 이런 경우가 무시되는거 같네요

chatterboy 9년 전 0

@movie_jo

답변 감사합니다 ! :D

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

문제

문제

출처

ICPC

2156 문제 질문입니다.

chatterboy 9년 전 0

movie_jo 9년 전 1

chatterboy 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말