[C] 백준 - 2156번: 포도주 시식

3월 16일(목) - 동적계획법 1 (2156번)

2156번: 포도주 시식

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 화요일날 풀었던 2579번: 계단 오르기 문제의 풀이와 거의 유사하다

- 연속 3잔을 마실 수 없고, (연속 3개의 계단을 밟을 수 없었고,)

- 마실 수 있는 최댓값을 구해야하기 때문이다 (계단을 밟아서 얻을 수 있는 점수의 최댓값을 구해야했다)

[C] 백준 - 2579번: 계단 오르기

- 하지만 이번 문제는 마지막 와인을 마시지는 않아도 된다

- 반면 2579번에서는 마지막 계단을 무조건 밟았어야한다

- 결국 마지막 n번째 입력된 값을 포함하지 않는 최댓값도 고려하는 조건을 2579번 풀이에 추가하면 된다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int MAX(int x, int y)
{
	return ((x > y) ? x : y);
}

int main(void)
{
	int wine[10001] = { 0, };
	int dp[10001];

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

	dp[0] = 0;
	dp[1] = wine[1];
	dp[2] = wine[1] + wine[2];
	for (int i = 3; i < n + 1; i++)
	{
		dp[i] = wine[i] + MAX(dp[i - 2], dp[i - 3] + wine[i - 1]);
		dp[i] = MAX(dp[i - 1], dp[i]); // n번째 값을 포함하지 않는 최댓값도 고려하는 조건
	}

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ