[백준/Python] 2156 포도주 시식

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

2156번: 포도주 시식

처음 세운 규칙은 

1. 현재 잔(w4)+이전 잔(-1)+전전 잔(-3)

2. 현재 잔(w4)+전전 잔(-2)+그이전 잔(-3)

이렇게 두가지 경우로 식을 세워서 풀어보았지만 실패! 

 

그래서 다른 분들의 백준 풀이를 찾아보니,

현재 잔을 마시지 않는 경우를 포함해야한다는 것을 깨달았다. 

 

1. 현재 잔(w4)+이전 잔(w3)+전전 잔(w1)

2. 현재 잔(w4)+전전 잔(w2)+그이전 잔(w1)

3. 현재 잔을 마시지 않고 이전의 케이스에서 최댓값을 가져오는 경우

이렇게 세가지 경우로 최종 식을 세워보았다. 

 

memo[0] = w[0]

memo[1] = w[0]+w[1]

0번째, 1번째 잔은 위와 같이 저장하고, 

2번째 잔부터는 현재 잔을 마시지 않는 경우를 포함하여 반복문을 작성했다. (최댓값을 저장할 배열 : memo[])

 

다만!

2번 잔의 경우, 잔의 개수가 2개일 때 인덱스 오류가 날 수 있으므로 아래와 같이 0, 1번째 잔과 함께 if문으로 따로 처리해주었다. 

(중간에 계속 오류가 나서 다른 분들의 코드를 보며 진행하였다ㅠ)

memo[2] = max(w[0]+w[2], w[1]+w[2], memo[1](=w[0]+w[1]))

memo[i] = max(memo[i-3]+wine[i-1]+wine[i], memo[i-2]+wine[i], memo[i-1]) >> 위의 세 가지 경우를 코드로 변환! 

 

최종 코드는 아래와 같다.

n = int(input())

wine = []
for i in range(n):
    wine.append(int(input()))

memo = [0]*n
memo[0] = wine[0]

for i in range(1, n):
    if i == 1:
        memo[1] = wine[0]+wine[1]
    #잔의 개수가 2개일 때 인덱스 오류가 날 수 있으므로 따로 처리
    elif i == 2:
        memo[2] = max(wine[i-2]+wine[i], wine[i-1]+wine[i], memo[1])
    else :
        memo[i] = max(memo[i-3]+wine[i-1]+wine[i], memo[i-2]+wine[i], memo[i-1])

print(memo[n-1])

---

코딩 테스트 대비 및 알고리즘 개념을 익히기 위해 다른 분들의 코드를 참고하며 반복학습 중입니다: )

해당 문제는 https://hongcoding.tistory.com/48 블로그를 통해 학습하였습니다.