글 읽기 - [파이썬] 이유가 궁금합니다!

kwonjoosung 1년 전 0

동적 프로그래밍을 공부하고 있는데 잘 이해가 가지 않아서 질문드립니다.

문제를 해결하긴 했는데 주석 친 부분에 있는 질문처럼 왜 3개의 값 중 최대 값을 고르는지 모르겠습니다. 밑 코드처럼 하면 안되는 이유가 뭔가요?

import sys

N = int(sys.stdin.readline())
arr = []
DP_arr = [0, 0, 0]
for _ in range(N):
    arr.append(int(sys.stdin.readline()))

if N >= 4:
    DP_arr[0] = arr[0]
    DP_arr[1] = arr[0] + arr[1]
    DP_arr[2] = max(arr[0] + arr[2], arr[1] + arr[2])
    for i in range(3, N):
        DP_arr.append(max(
            DP_arr[i - 2] + arr[i], DP_arr[i - 3] + arr[i - 1] + arr[i]))
        # 여기에 DP_arr[i-1] 추가 되어야 하는 이유?
    print(max(DP_arr[N - 1], DP_arr[N - 2]))
elif N == 3:
    print(max(arr[0] + arr[2], arr[1] + arr[2]))
elif N == 2:
    print(arr[0] + arr[1])
else:
    print(arr[0])

yijw0930 1년 전 0

대충 해도 되는 이유에 대해서는 아실 것 같으니 안하면 안 되는 반례는 다음과 같습니다.

kwonjoosung 1년 전 0

아 0을 고려하지 못했네요,, 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 이유가 궁금합니다!

kwonjoosung 1년 전 0

yijw0930 1년 전 0

kwonjoosung 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말