[파이썬][백준 2156][🤍실버 1] (다이나믹 프로그래밍)

🧞‍♂️ 난이도

🤍 실버 1

🧞‍♂️ 문제

포도주 시식

https://www.acmicpc.net/problem/2156

🧞‍♂️ 유형

다이나믹 프로그래밍

🧞‍♂️ 내 풀이

이 문제는 다이나믹 프로그래밍으로 풀면 되는 문제이다.

마지막 잔을 비운다고 생각했을때 (array[n])

1. …array[n-3] + array[n-2] + array[n]
2. …array[n-3] + array[n-1] + array[n]

두 경우의 수를 점화식으로 표현하면

1. dp[i] = dp[i-2] + array[i]
2. dp[i] = dp[i-3] + array[i-1] + array[i]

이렇게 세워두고, for 문안에서 max 이용해서 dp에 최대값 갱신하면 된다.

for i in 3..<N {
    dp[i] = max(dp[i-2] + array[i], dp[i-3] + array[i-1] + array[i])
}

고 생각했는데 틀렸다.. 여기서 계속 헤매다가 예외 케이스를 발견했는데 100, 100, 0, 0, 100, 100 이럴때는 가운데 0 두개를 제외한 잔을 비우는 것이 최대값이 된다.

그래서 마지막에 dp[i-1]이랑 dp[i] 를 비교해줘야한다.

왜 배열들 크기를 N 으로 잡으면 안되고 10000 으로 하면 되는지 의아했었는데, N = 1일때 인덱스 오류가 발생하기 때문인것 같다.

---

🧞‍♂️ 파이썬 풀이

import sys
input = sys.stdin.readline

N = int(input())
arr = [0] * 10000
for i in range(N):
    arr[i] = int(input())

dp = [0] * 10000
dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(dp[1], arr[0] + arr[2], arr[2] + arr[1])

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

print(dp[N-1])

🧞‍♂️ 특이했던 다른 사람 스위프트 풀이

readLine()
var arr = [0,0,0]
arr[0] = Int(readLine()!)!

while let input = readLine() {
    let wine = Int(input)!
    let t = arr[2]

    arr[2] = max(arr[0], arr[1], arr[2])
    arr[1] = arr[0] + wine
    arr[0] = t + wine
}

print(arr.max()!)

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기