2156 포도주 시식 dp

Kyung yup Lee·2021년 1월 22일
0

알고리즘

목록 보기
9/33

실1

해당 문제는 dp의 바텀업 방식으로 풀어내는 문제이다.

난이도가 올라갈수록 바텀업을 잘 풀어낼 수 있어야 될 것 같은 직감이 든다.

바텀업 방식은 점화식을 만들어서 풀어야 한다고 하는데, 꼭 점화식을 만들 수 있어야 하지는 않다.

n을 1부터 하나씩 증가시켜가면서 규칙성을 찾기만하면 그걸 코드로 구현해낼 수 있다.

풀이

먼저 n이 1일 경우를 생각해본다. 최대값은 첫번째 잔만 선택하므로 6이다.

n이 2일 경우 최대값은 첫번째 잔 두번째 잔을 더해서 16이다.

n이 3일 경우 (첫번째 잔, 세번째 잔), (첫번째 잔, 두번째 잔), (두번째 잔, 세번째 잔) 조합중 최대값을 선택한다.

여기까지만 봐도 대충 3개 중 최대값을 구하게 되겠다고 느낌이 오면 좋다. 안와도 된다.

n이 4일 경우 (네번째 잔, 세번째 잔, 첫번째 잔(까지의 최대값)), (네번째 잔, 두번째 잔까지의 최대값), (세번째 잔까지의 최대값) 중 최대값을 구해야 한다.

이 규칙은 n이 커져도 똑같다.

해당 내용을 코드로 구현하면

    ans[i] = max(arr[i] + arr[i-1] + ans[i-3], ans[i-1], arr[i] + ans[i-2])

n번째 값마다 최대값이 들어가는 리스트를 만들고, 이 리스트를 이용해 커지는 n 값을 계속 구해 나간다.

n = int(input())
arr = [0]
for _ in range(n):
    arr.append(int(input()))
ans = [0] * (n+1)

def solution():
    ans[1] = arr[1]
    if n > 1: 
        ans[2] = arr[2] + arr[1]

    if n > 2:
        for i in range(3, n+1):
            ans[i] = max(arr[i] + arr[i-1] + ans[i-3], ans[i-1], arr[i] + ans[i-2])
    print(max(ans))

solution()
profile
성장하는 개발자

0개의 댓글