백준 2038 골룽 수열 (파이썬)

문제 : https://www.acmicpc.net/problem/2038

골룽 수열은 1이 1개, 2가 2개 있으니 2번, f(3) = 2 이므로 3이 2번 나타나는 단조 증가하는 수열입니다.

수열을 숫자로 풀면 다음과 같습니다.

[1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8..]   

 

첫번째 제출 (시간초과)

import sys

def solve(dp):
    left = 1
    right = 0
    k = 3
    while len(dp) < n:
        dp = dp + [k]*(dp[left])
        left += 1
        k = k+1
    print(dp[n-1])
    return

if __name__=="__main__":
    n = int(sys.stdin.readline())
    dp = [1, 2, 2]
    solve(dp)

 

N이 최대 20억 이라서 DP의 크기를 계산 못할 것 같아 DP를 계속 추가해주는 방식으로 풀었는데 시간초과가 발생했습니다.

 

두번째 제출 (정답)

import sys

def solve(dp):
    dp[1] = 1
    SUM = dp[1]
    i = 1
    while SUM < n:
        i += 1
        dp[i] = 1 + dp[i - dp[dp[i - 1]]]
        SUM += dp[i]

    print(i)
    return

if __name__=="__main__":
    n = int(sys.stdin.readline())
    dp = [0] * (1000001)
    solve(dp)

 

결과 및 정리

정답을 전혀 못 찾겠어서 검색을 해서 힌트를 얻었습니다.

골룽 수열의 점화식은 다음과 같습니다.

dp[i] = 1 + dp[i - dp[dp[i - 1]]]

n을 i와 비교하지 않고 SUM과 비교하는 이유는 일단 i와 비교하면 20억번 계산해야하는데 이는 시간초과가 무조건 발생합니다.

따라서 비교하는 방법을 다르게 해야하는데

n = 5라면 골롱 수열은 1, 2, 2, 3, 3 이므로 f(5) = 3 이다. 그리고 i = 3 일때 sum 은 5 이므로 i로 f(n)을 찾을 수 있습니다.

(정확한 이유는 저도 잘 모르겠습니다.)