[백준] 2156번 : 포도주 시식 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2156번: 포도주 시식

 

1. 문제 설명

2. 풀이과정

해당 문제는 포도주를 최대한 마시는 방법을 구해야 한다.

잔을 마실 때는 이전의 마신 결과를 확인해야 하므로 이전에 마신 결과가 다음 잔에 영향을 준다.

하여 다이나믹 프로그래밍으로 문제를 해결하였다.

포도주를 마실 수 있는 경우는 3개의 잔을 봤을 때 1번과 3번 잔을 마시는 경우(OXO), 1번과 2번 잔을 마시는 경우(OOX), 2번과 3번 잔을 마시는 경우(XOO)로 나눌 수 있다.

이 3가지 경우를 매 잔을 마시기 전에 확인하고 가장 많이 마실 수 있는 경우를 선택하면 된다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 포도주 잔의 개수를 입력받는다. n = int(sys.stdin.readline())
3. 각 잔의 포도주 양을 저장할 리스트를 생성하고 volume = list()
4. 각 잔에 들어있는 포도주의 양을 입력받아 추가한다. for _ in range(n): volume.append(int(sys.stdin.readline()))
5. 만약 포도주가 1잔 이하라면 if (len(volume) <= 1)
6. 그냥 그 잔을 마시므로 해당 잔에 들어있는 포도주의 양을 출력한다. print(volume[0])
7. 반면에 포도주가 2잔 이상으로 있다면 else
8. 최대로 마실 수 있는 포도주의 양을 저장할 리스트를 포도주 잔의 개수만큼 생성하고 모두 0으로 초기화한다. result = [0] * n
9. 첫 번째는 그냥 첫 번째 잔을 마신 결과를 저장한다. result[0] = volume[0]
10. 두 번째는 첫 번째 잔과 두 번째 잔을 마신 결과를 저장한다. result[1] = volume[0] + volume[1]
11. 세 번째 결과부터는 반복문을 사용하여 구하는데 for i in range(2, n)
12. 첫 번째 경우는 OXO의 경우로 포도주를 마신 경우이고 case1 = result[i - 2] + volume[i]
13. 두 번째 경우는 OOX의 경우로 포도주를 마신 경우이며 case2 = result[i - 1]
14. 세 번째 경우는 XOO의 경우로 포도주를 마신 경우이다. case3 = result[i - 3] + volume[i - 1] + volume[i]
15. 세 가지 경우 중 가장 많은 포도주를 마시는 경우를 저장한다. result[i] = max(case1, case2, case3)
16. 최종 결과를 구했다면 가장 마지막의 포도주 양이 제일 크므로 출력한다. print(result[-1])

반응형

3. 소스코드

import sys

n = int(sys.stdin.readline())

volume = list()
for _ in range(n):
    volume.append(int(sys.stdin.readline()))

if (len(volume) <= 1):
    print(volume[0])
else:
    result = [0] * n
    result[0] = volume[0]
    result[1] = volume[0] + volume[1]
    for i in range(2, n):
        case1 = result[i - 2] + volume[i]
        case2 = result[i - 1]
        case3 = result[i - 3] + volume[i - 1] + volume[i]

        result[i] = max(case1, case2, case3)

    print(result[-1])