방학공부 3일차

기재를 하지 않았었는데 현재 풀고있는 문제들은 Plzrun님의 "알고리즘 문제풀이(ps) 시작하기" 를 참고하여 선정하였습니다. 포스트 링크

문제 : 백준 2156번
알고리즘 : DynamicProgramming

문제에 따르면 N개의 포도주 잔 중에 i번째 잔에 대해 가능한 경우는 3가지이다.

case 0 : 마시지 않는다
case 1 : i - 1번째 잔을 마시지 않고 i번째 잔을 마신다
case 2 : i - 1번째 잔을 마시고 i번째 잔을 마신다.

case0,1,2 를 나타낼 리스트를 세 개 만들어 각각 연산한다.

ex) case1[4] : 3번째 잔은 마시지 않고 4번째 잔을 마실 때, 최대로 마실 수 있는 포도주의 양
ex) case2[7] : 6, 7번째 잔을 마실 때, 최대로 마실 수 있는 포도주의 양

case 0의 i번째 항 : case0[i - 1], case0[i - 1], case2[i - 1] 중 최대값 선택
case 1의 i번째 항 : i-1번째 잔을 마시지 않았어야 하므로 case0[i - 1] + i번째 잔의 양 과 같음
case 2의 i번째 항 : i - 1번째 잔을 마셨어야하므로 case1[i-1] + i번째 잔의 양 과 같음

N번째 항까지 case0~2의 연산을 마치고 리스트들의 마지막 항들 중 가장 큰 값이 최대로 마실 수 있는 포도주의 양이다.

import sys
input = sys.stdin.readline
glass = []
sum = 0
#main
N = int(input())
for i in range(N):
    glass.append(int(input()))

if N <= 2 :
    for el in glass :
        sum += el
else :
    case0 = [0 for i in range(N)]
    case1 = [0 for i in range(N)]
    case2 = [0 for i in range(N)]
    
    case0[1] += glass[0]
    case1[1] += glass[1]
    case2[1] += glass[0] + glass[1]

    for i in range(2,N):
        case0[i] += max(case0[i-1],case1[i-1],case2[i-1])
        case1[i] += (case0[i-1] + glass[i])
        case2[i] += (case1[i-1] + glass[i])
    sum = max(case0[N - 1],case1[N - 1],case2[N - 1])

print(sum)

인덱스 표기로 i = N - 1까지 반복문을 진행한다.

N이 2이하이면 3잔이상 연속으로 마실 수 없으므로 그냥 총합을 출력하면 된다.
최대값을 골라내는데는 max()함수를 사용하였다.

종합평가

시간복잡도 : O(n)
소요시간 : 10~15분
실패횟수 : 0