[백준 17968번] [동적 계획법/에라토스테네스의 체] Fire on Field

이 문제의 경우는 모든 떨어진 거리가 정수인 것에 대하여 등차수열 관계가 이루지 못하게끔 하는 최솟값을 물어보는 것이다.

 

최솟값을 구해야하기 때문에 불가능한 것들을 모두 지우고 나머지 중에 최소를 구하는 것이 가장 현실적인 것을 깨달아야 한다.

그러면 문제에서 0~ 1000까지라고 하였으므로 배열을 미리 0~ 1000까지 설정하고 에라토스테네스의 체 논리처럼 슥슥 지워나가는 방향으로 하는 것이 가장 타당하다고 생각해야 한다.

 

또한, 고등학교때 배운 것처럼 등차수열의 3개의 항의 관계는 중앙값의 2배가 양 옆 수열의 합과 같다는 것이다. 이를 기반으로 불가능한 후보를 확보할 수 있다.

 

이 과정에서 이전 수열들에 대한 정보가 필요하게 되므로 이 지점에서 DP가 유리하다는 것을 인식하면 된다.

 

이를 기반으로 코드를 짜면 다음과 같다.

import sys

# Initial setting

data_store = [0] * 1001
data_store[0] = 1
data_store[1] = 1
n = int(input())

# Start with small value

l = 2

while l <= n:

    # Default setting (True)

    data = [True] * 1001

    # Erase impossible value

    k = 1
    while l - 2 * k >= 0:
        data[data_store[l - k] * 2 - data_store[l - 2 * k]] = False
        k += 1

    # Find the minimum value and save it 

    for i in range(1, 1002):
        if data[i] == True:
            data_store[l] = i
            break
        else:
            pass

    l += 1    

# Print result

print(data_store[n])
Colored by Color Scripter

계속해서 N번째 수를 구하기 위해서는 앞의 정보를 알아야 한다는 것을 기반으로 DP를 의심하고, 이를 활용하기 위한 방법으로 등차수열의 성질이나 에라토스테네스의 체 방법을 강구하였다고 보는 것이 가장 타당하다.

 

필연적으로 어떻게 하면 이런 방식으로 사고할 수 있는지 지속적으로 점검할 필요성이 존재한다.