[Python] 백준 2156번_ 포도주 시식

문제 

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

2156번: 포도주 시식

특이점 

1. 처음엔 배열의 길이, 그 다음부터 각 줄마다 배열의 요소를 입력한다. 각 요소값은 1000 이하의 음이 아닌 정수.
2. 포도주가 일렬로 나열된다. → 1차원 배열을 이용한다.
3. 연속으로 3개의 수를 고를 수 없다.
4. 총 합이 최대가 되는 수를 골라야한다.
5. 위 조건들을 고려해봤을 때, 마지막 수를 포함한다고 무조건 최대값이 나오는 것은 아니다.

코드

cnt = int(input())

w = [0]*10000
for i in range(cnt):
    w[i]=int(input())

dp= [0]*10000
dp[0]=w[0]
dp[1]=w[0]+w[1]
dp[2]=max(dp[1],max(w[0],w[1])+w[2])
for i in range(3,cnt):
    dp[i]=max(dp[i-2]+w[i], dp[i-3]+w[i-1]+w[i], dp[i-1])
print(max(dp))

풀이 

• 와인에 대응하는 숫자가 담길 배열 w를 미리 생성 (잔 개수 1개~10000개 사이)
• 최대값이 담길 배열dp도 생성, n개의 포도주 양을 입력했을 때(~w[n-1]), 가능한 최대값을 저장할 dp[n-1]을 갱신해줌

A

B

C

D

E

• 연속해서 3개를 고를 수 없는 점을 고려했을 때, 최대값이 나올 수 있는 경우는 크게 3가지이다.
  
  • 1) 마지막 2개(D,E)를 무조건 고를 경우 >> C는 무조건 제외해야 함
    • 따라서 B까지의 경우 중 최대값 (=dp[1]) + D(=w[3]) + E(=w[4])
  • 2) E는 고르되, D를 무조건 제외하는 경우 >> C는 선택가능
    • 따라서, C까지의 경우 중 최대값(=dp[2]) + E(=w[4])
  • 3) E를 선택하지 않는경우
    • E를 제외한 그 앞자리까지의 최대값과 동일 (=dp[3])
  • ⇒ 이것들 중 최대값을 구하면 그것이 곧 dp[4]이다.

• [정리] dp[n] = max( dp[n-3]+w[n-1]+w[n] , dp[n-2] + w[n] , dp[n-1] )  

---

• [예외 경우] n=0, 1, 2의 경우
  
  • n = 0 → dp[0] = w[0]
  • n = 1 → dp[1] = w[0] + w[1]
  • n = 2 → dp[2] = max( dp[1], max(w[0], wp[1]) + w[2] ) 
    • 1) w[0] + w[1]이 최대값일 때 >> dp[1]
    • 2) w[0] or w[1] + w[2]  이 최대값일 때 >> max(w[0], wp[1]) + w[2]

다른 풀이 

 출처: https://www.acmicpc.net/source/14324613

import sys


def sol(n, wine):
    a, b, c = 0, 0, 0
    for i in wine:
        a, b, c = max(a, b, c), a + i, b + i
    return max(a, b, c)


if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    wine = [int(input()) for _ in range(n)]
    print(sol(n, wine))

→ 최대값을 구하는 기능을 함수로 구현함

• 변수 3개를 정의해, 갱신해주는 형식
• wine[0] >> a,b,c = 0, wine[0], wine[0]
• wine[1] >> a,b,c = wine[0] , wine[1], wine[0]+wine[1]
• wine[2] >> a,b,c = wine[0]+wine[1], wine[0]+wine[2], wine[1]+wine[2]
• wine[3] >> 만약, wine[0]+wine[1]이 최대값인경우,
  • a,b,c = wine[0]+wine[1], wine[0]+wine[1]+wine[3], wine[0]+wine[2]+wine[3]
  • ⇒ a,b,c = dp[n-1], dp[n-2] + w[n], dp[n-3]+w[n-1]+w[n] 
  • 이렇게도 구현 가능하군...!