[BOJ] 2156번 포도주 시식 / 사용언어 : 파이썬(python)

※ 문제링크 

2156번: 포도주 시식

※ 참고 사이트

[백준] 2156번(python 파이썬)

해당 문제는 규칙을 확인하고 동적프로그래밍을 이용하여 푸는 문제였다. 규칙이 생각보다 어려워서 구상하는데 꽤나 오랜시간이 걸렸지만, 규칙을 확인하고 구현하는 것은 규칙을 찾는 것보다는 쉬웠다. 해당 문제는 계단오르기 문제와 굉장히 유사한 문제이다.내가 찾은 규칙으로 문제를 풀었더니 통과는 되었지만 시간이 오래걸리는 듯하여 구글링을 통해 다른 코드를 살펴보던 중 좋은코드가 있어서 해당 코드를 보며 학습했다.

<풀이방법>

- 첫번째에서 가질 수 있는 값은 자기 자신과 동일 / 2번째는 첫번째와 두번째의 합과 동일

- 세번째가 가질 수 있는 최댓값 : 첫번째와 세번째를 더한 값과 두번째와 세번째를 더한값 중 큰 값

- 4번째부터는 2개의 값을 지속적으로 비교하여 값을 추출 : 

   max(i-2까지의 값들 중 최댓값(dp) + i의 값(num), i-3의 값들 중 최댓값(dp) + i-1의 값(num) + i의 값(num))

1. 계단마다 가지는 값들 저장할 리스트와 해당 계단의 층수에서 가질 수 있는 최댓값을 저장할 dp리스트를 생성한다.

2. 규칙을 적용하여 반복문을 돌린 후 dp에서 마지막 값을 출력

+ 원소의 갯수가 3이하일 경우에는 조건문을 걸어서 처리해주어야 IndexError가 나지 않습니다.

 

N = int(input())
grape = [int(input()) for _ in range(N)]
dp = [0 for _ in range(N)]
if N < 2:
    dp[0] = grape[0]
elif N < 3:
    dp[0] = grape[0]
    dp[1] = grape[0] + grape[1]
else:
    dp[0] = grape[0]
    dp[1] = grape[0] + grape[1]
    dp[2] = max(dp[0] + grape[2], grape[1] + grape[2])
    for i in range(3, N):
        dp[i] = max(max(dp[:i-1]) + grape[i], max(dp[:i-2]) + grape[i-1] + grape[i])
print(max(dp))

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.