글 읽기 - 2156 포도주 질문드립니다. 초보좀 도와주세요 ㅠㅠ

leedh2004 5년 전 1

점화식을 dp[n][k] 는 n잔의 포도주가 있고 현재 k잔 연속으로 마셨을 때 먹은 최대 포도주양 으로 잡았습니다.

따라서 dp[n][0] = max(dp[n-1][0], dp[n-1][1], dp[n-2][2])

dp[n][1] = dp[n-1][0] + n번째 포도잔

dp[n][2] = dp[n-1][1] + n번째 포도잔

이라고 생각했는데 어느 부분에서 잘못생각하고 있는지 잘 모르겠습니다..

도와주시면 감사하겠습니다ㅠㅠ.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int arr[11111];
int dp[11111][3];

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

int main() {

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

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

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

	printf("%d", max(max(dp[n][0], dp[n][1]), dp[n][2]));
	return 0;
}

bupjae 5년 전 0

dp[2][0] = arr[1]

leedh2004 5년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

2156 포도주 질문드립니다. 초보좀 도와주세요 ㅠㅠ

leedh2004 5년 전 1

bupjae 5년 전 0

leedh2004 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말