2579

날짜 : 2022. 11. 13

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
s = [] # 계단에 쓰여진 숫자
dp = [0] * 301 # 해당 자리까지의 점수의 최댓값

for _ in range(n): s.append(int(sys.stdin.readline()))

if n == 1: print(s[0])
elif n == 2: print(s[0]+s[1])
else:
    dp[0] = s[0] # 0인 경우 해당 칸만 적용
    dp[1] = s[0] + s[1] # 1인 경우 0, 1만 적용
    for i in range(2, n):
        dp[i] = max(dp[i - 2] + s[i], dp[i - 3] + s[i - 1] + s[i]) # 1칸 이동해서 도착한 경우와 2칸 이동해서 도착한 경우 비교
    print(dp[n - 1])
    #print(dp[:n]) # 디버깅

 

풀이

- 가장 마지막 자리에서부터 역순으로 시작해서 풀이하려고 했지만 너무 복잡해서 고민끝에 다른 풀이들을 참고했다.

- 처음부터 시작하되, n값이 3이상인 케이스부터는 for문을 통해 다이나믹 프로그래밍을 이용해서 문제를 해결하는 방식이었다.

- 먼저 첫번째, 두번째의 경우는 주석처럼 풀이하면 되고, 3번째부터는 해당 칸까지 한 칸을 이동했을 경우와 두 칸을 이동했을 경우를 서로 비교해서 최댓값을 설정해 주면 된다.

 

 

 

알게된 점

- 여기서 dp[i] = max(dp[i - 2] + s[i], dp[i - 3] + s[i - 1] + s[i]) 를 확실하게 이해하지 못해 꽤 많은 고민을 했었다.

- 그리고 dp를 통해 이전값들을 저장하는 방식 또한 곧바로 떠올리지 못했다는 것이 아쉬웠다.

- 오는 주차에는 다이나믹 프로그래밍 문제를 좀 많이 풀어보아야겠다.

 

 

 

참고 사이트

-