[알고리즘] 2156 포도주 시식 (Python)

yujin37·2023년 3월 24일
0

문제분석

문제


이 문제는 포도주를 마시는데 연속으로 3잔을 마실 수 없도록 규칙을 두고 있다. 그래서 이 포도주를 선택을 잘 맞추어서 가장 많은 양을 마실 수 있도록 해주어야 한다. DP라는 것을 눈치를 챌 수 있을 것이다.

입력과 출력


입력과 출력 설명을 보자. 첫쨋줄에 포도주 잔의 개수가 주어지고 이어서 나오는 줄에는 포도주의 양을 넣어준다. 이렇게 넣은 값으로 최대로 마실 수 있는 포도주의 양을 출력해주면 된다.

예제


예제는 다음과 같다.
6잔을 입력받기로 하였고 6,10,13,9,8,1 순으로 받고 있는 것을 확인할 수 있다. 여기서 마실 수 있는 최대 포도주의 양은 33이라고 한다.

코드 분석

각 와인잔의 양

n=int(input())
cup=[0 for _ in range(10000)]
for i in range(n):
    wine=int(input())
    cup[i]=wine

그럼 이제 코드를 작성해보자. 일단 입력 부분을 작성해주고 포도주 양을 입력받는 리스트를 만들어준다. 처음에는 이 부분을 작성할 때 리스트를 n의 값으로 만들어주었는데 0이라는 예외사항 때문인지 이렇게 문제 조건대로 10000으로 해주어야 에러가 나지 않았다.

그리고 와인잔에 담기는 양들을 for문으로 받아낸다.

초기 DP 설정

result=[0]*10000
result[0]=cup[0]
result[1]=cup[0]+cup[1]
result[2]=max(cup[0]+cup[2],result[1],cup[1]+cup[2])

DP의 핵심! 초기설정이다.
일단 결과도 앞에 cup리스트를 만들어준 것 처럼 크기를 만들어준다. 그리고 인덱스 0에는 컵의 첫번째 인덱스를 넣어준다. 1에는 컵의 0과 1 인덱스를 더해서 넣는다. 2에서는 이제 인덱스0+인덱스2, 인덱스0+인덱스1, 인덱스1+인덱스2 값 중에서 비교를 해주어야 한다.
이렇게 해야 하는 이유는 최댓값을 만들기 위해서이다. 연속된 값이 3개를 넣을 수 없기 때문에 각 방법에 따라 어떤 방법이 최대인지 비교를 해주어야 한다.

이후 규칙

for i in range(3,n):
    result[i]=max(result[i-2]+cup[i],result[i-1],cup[i]+cup[i-1]+result[i-3])

인덱스 3부터는 for문으로 처리하면 된다. 앞에 보았던 인덱스 2에서의 비교를 i라는 것을 통해 만든 것을 확인할 수 있다. 여기서 다른 것은 max 비교 중 가장 끝인 cup[i]+cup[i-1]+result[i-3] 이 부분이다. 3을 가정으로 하면 cup[3]+cup[2]+result[0], 즉 cup[1]을 제외하고 넣는 것을 발견할 수 있다. 이 방식으로 계속 갱신을 해준다.

주의사항

cup=[0 for _ in range(10000)]
result=[0]*10000

앞에서도 언급하긴 했지만 이부분 때문에 정답 제출시 오답으로 나왔다. 조건처럼 10000으로 하면 비효율적으로 보이긴 했지만 오답이 안나오기 위해서는 10000으로 넣어주어야 한다.

최종 코드

n=int(input())
cup=[0 for _ in range(10000)]
for i in range(n):
    wine=int(input())
    cup[i]=wine
result=[0]*10000
result[0]=cup[0]
result[1]=cup[0]+cup[1]
result[2]=max(cup[0]+cup[2],result[1],cup[1]+cup[2])
for i in range(3,n):
    result[i]=max(result[i-2]+cup[i],result[i-1],cup[i]+cup[i-1]+result[i-3])
print(max(result))

모두 합친 코드는 다음과 같다.
마지막에 최댓값을 출력하면 와인을 가장 많이 마실 수 있는 양이 출력된다.

결론

문제 분류를 통해 DP라는 것을 어느정도 인지를 했지만 max부분에 어떻게 값을 조합할 것인가가 어려웠다. 이 형태가 두개까지는 한들었는데 max 값중 제일 끝부분을 생각해내는 과정이 오래걸렸다.
그리고 10000부분때문에 계속 틀렸다고 나왔던 것. 이 두가지만 쉽게 해결된다고 하면 쉽게 설계할 수 있지 않을까 싶다.
풀어도풀어도 DP는 아직 완벽하지 않은 것 같다. ㅎㅎ

profile
💻 하고싶은 것이 많은 사람

0개의 댓글