[BOJ][Python][실3][2156] 포도주 시식

문제 링크

문제링크

첫 번째 풀이

dp[i][j] : j번째까지 포함해서, 연속해서 먹은 포도주의 수가 i개인 경우의 답

i는 0~2으로 j번째 포도주를 먹지 않은 것까지 고려해야 합니다.

정답코드

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
import copy

# sys.stdin = open("input.txt", "r")

n = int(input())
arr = list(map(int, sys.stdin.read().splitlines()))
dp = [[0] * n for _ in range(3)]

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

for i in range(1, n):
    dp[0][i] = max(dp[0][i - 1], dp[1][i - 1], dp[2][i - 1])
    dp[1][i] = dp[0][i - 1] + arr[i]
    dp[2][i] = dp[1][i - 1] + arr[i]

print(max(dp[0][n - 1], dp[1][n - 1], dp[2][n - 1]))

백준님 풀이 : 1차원 DP

dp[i] : i번째 와인까지 시식했을 때 최대 먹은 양

1. i번째부터 봤을 때 최근에 0개를 연속해서 먹은 경우 ???X
2. i번째부터 봤을 때 최근에 1개를 연속해서 먹은 경우 ??XO
3. i번째부터 봤을 때 최근에 2개를 연속해서 먹은 경우 ?XOO

a = dp[i-1]; b = dp[i-2] + v[i]; c = dp[i-3] + v[i-1] + v[i];

dp[i] = max(a,max(b,c))

코드

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
import copy

# sys.stdin = open("input.txt", "r")

n = int(input())
arr = list(map(int, sys.stdin.read().splitlines()))
dp = [0] * 10010

'''
dp[i] i번째까지 최대 먹은 양

i번째 까지 연속 0개 먹은 경우 : ???X
i번째 까지 연속 1개 먹은 경우 : ??XO
i번째 까지 연속 2개 먹은 경우 : ?XOO

a = dp[i-1]
b = dp[i-2] + arr[i]
c = dp[i-3] + arr[i-1] + arr[i]
dp[i] = max(a,b,c)
'''

if n == 1:
    print(arr[0])
    exit(0)
elif n == 2:
    print(arr[1] + arr[0])
    exit(0)

dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(dp[1], arr[0] + arr[2], arr[1] + arr[2])
for i in range(3, n):
    a = dp[i - 1]
    b = dp[i - 2] + arr[i]
    c = dp[i - 3] + arr[i - 1] + arr[i]
    dp[i] = max(a, b, c)
print(dp[n - 1])

```cpp

#include #include using namespace std; long long v[10001]; long long dp[10001]; int n;

int main(void) { scanf(“%d”, &n); for (int j = 1; j <= n; j++) { scanf(“%lld”, &v[j]); } long long a, b, c; dp[1] = v[1]; dp[2] = dp[1] + v[2]; a = dp[2]; b = dp[1] + v[3]; c = v[2] + v[3]; dp[3] = max(a, max(b, c));

for (int i = 4; i <= n; i++) {
	a = dp[i - 1];
	b = dp[i - 2] + v[i];
	c = dp[i - 3] + v[i - 1] + v[i];
	dp[i] = max(a, max(b, c));
}

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

Success Notice: 수고하셨습니다.