[Python 3] BOJ 25759 들판 건너가기

오늘의 문제는 들판 건너가기라는 문제이다.

굉장히 간단하고 명료한 문제이다.

문제를 보자마자 DP를 써야겠다라는 생각이 들었다.

하지만, 구체적으로 어떤 방안을 사용해서 구현해야할지 고민이 되었다.

 

"아름다움 값 A_i"이 100개밖에 없는 상황이다. 이를 역이용해서 DP를 구현해보았다.

 

n=int(input())
data=[0]+list(map(int,input().split()))
dp=[-1e10 for _ in range(101)]
dp[data[1]]=0
for i in range(2,n+1):
    for j in range(1,101):
        if dp[j]!=-1e10:
            dp[data[i]]=max(dp[data[i]],dp[j]+(data[i]-j)**2)
print(max(dp))

 

dp 테이블을 크기가 101인 리스트로 선언하였다.

dp의 정의를 "i번째 index에서 data[i]번째 꽃을 골랐을 때, 가능한 아름다움의 최댓값으로 정의하였다."

 

dp 테이블의 초깃값을 모두 -1e10으로 두었다. (1e10이란 scientific notation으로 0이 10개 있는 10의 10제곱. 보통 import math 이후 math.inf의 값을 대신 할 때 1e10을 사용한다.)

 

즉, data[i]에서의 값과, j와 값을 비교해서 (전에 꽃이 j이일 때, 가장 크게 만들어진 아름다움의 값), 가능한 제일 큰 dp[i]가 무엇일지 계산한다. 

 

그림을 통해 설명하겠다. 

먼저, data 중 맨 첫번째 index인 1을 0으로 바꿔준다. 당연히 1이라는 수 한 개 가 있으면 아름다움은 0일 것이다.

이후 i가 2일 때, j가 1이면 아까 0으로 초기화했던 dp[1]과 차이가 1이 나기 때문에 dp[2]의 값은 1이다.

마지막으로 i가 3번째 인덱스일 때, 즉 3번째 꽃 (값은 3)을 고르고 1번째 인덱스를 고르면, 3-1 (값의 차이), 아름다움은 4가 된다.

만약 i가 3번째 인덱스이고, j의 값이 2이면, 차이가 1이므로 1을 더 추가할 수 있다. dp[1]가 1이므로, dp[3]의 값은 2라는 계산이 나오는데, 이미 4가 있으므로 값의 변화가 이루어지지 않는다. 

 

dp의 모든 인덱스 중 제일 큰 값을 정답으로 내뱉는다.