[파이썬(python)] 이것이 취업을 위한 코딩테스트다 개미 전사

나의 답안

풀면서도 왠지 모를 찜찜함이 있었다..

이것이 과연 max 답안일까?

 

n = int(input())
k = list(map(int, input().split()))

max_answer = 0

for i in range(len(k)):
    answer = 0
    answer += k[i]

    for j in range(i+2,len(k),2):
        answer += k[j]

    max_answer = max(answer, max_answer)

print(max_answer)

 

입력 예시에는 올바른 답이 출력됐지만

더많은 테스트 케이스가 있으면 틀릴 거라는 생각이 들었다.

지금 보고 있는데 그 말이 맞는듯..

 

이문제는 다이나믹 프로그래밍 문제이기 때문에,

문제를 작은 문제로 쪼개고 결과 값을 미리 저장해둔 다음

그 저장된 결과들을 이용해 메모리와 시간을 줄인다....

 

그리고 그 과정에서 점화식이라는 게 필요하다.

 

 

 

그러면 진짜 답안은 이렇게 된다.

d[0]와 d[1]는 0까지의 최적의 해, 1까지의 최적의 해이기 때문에 간단하게 구할수 있고

 

그 다음에는 d[i]에 d[i-1] 혹은 d[i-2]+k[i] 중 max값을 골라 저장하면 된다

d[n-1]가 최종적으로 인덱스 n-1까지의 최적의 해가 됨..

 

다음주에는 다이나믹 프로그래밍 문제를 복습해봐야겠다.

 

n = int(input())
k = list(map(int, input().split()))

d = [0] * len(k) #결과를 저장하는 배열

d[0] = k[0]
d[1] = max(k[0], k[1])

for i in range(2, n):
    d[i] = max(d[i-1], d[i-2]+k[i])

print(d[n-1])