코드

n = int(input())

def solution(n):
    # 모든 수는 1의 제곱수로 표현 가능
    # 따라서 DP 테이블을 해당 수로 초기화 시킴
    # 3 => 1 + 1 + 1 총 3개 => DP[3] = 3
    dp = [x for x in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, i):

#             if j*j <= i:
#                 if dp[i] > dp[i - (j*j)] + 1:
#                     dp[i] = dp[i-(j*j)] + 1
            
            # 위가 아닌 아래처럼 하면
            # j*j가 i보다 큰 경우에 대해선
            # 반복 자체를 수행하지 않으므로
            # 시간을 더 절약할 수 있음
            if j*j > i:
                break
                
            if dp[i] > dp[i - (j*j)] + 1:
                dp[i] = dp[i-(j*j)] + 1
    print(dp[n])                    
    
solution(n)

문제 해설

DP 문제

문제의 점화식을 유추하는 과정을 적어보면 아래와 같다.

  • n까지의 수를 나열하고 이를 제곱수로만 표현할 때, 4, 9, 16과 같이 새로운 제곱수가 등장할 때 DP 테이블의 값이 1로 초기화 된다. (16 => 4^2 ==> 1개)
  • 따라서 DP[i]를 구하는 경우 DP[i] 전에 등장한 제곱수를 뺀 DP[i - (j*j)]의 값에 +1을 해주면 그 값이 바로 DP[i]의 값이 된다.
  • 단, DP[i]가 한 번 갱신된 후에, DP[i - (j*j)]를 다시 비교할 때, 기존의 DP[i]값이 더 작을 수 있으므로 if문으로 해당 조건을 걸러낸다.

n까지의 숫자를 제곱수 합으로 표현하는 것을 손으로 직접 적어봐도 단번에 규칙을 파악하긴 어려운 문제이다. 따라서 좀 더 면밀하게 생각을 해봤을 때, 위의 규칙들을 알아낼 수 있었다.

DP 문제 자체가 이전까지 주어진 더 작은 경우의 수들을 조합하여 풀고자 하는 더 큰 문제를 해결하는 방식의 풀이 기법이다. 이걸 잘 이해하지 못 한다면 DP 문제는 쉽든 어렵든 푸는 입장에선 다른 알고리즘 문제들과는 다르게 접근하는 것 자체가 많이 힘든 것 같다. 기초부터 탄탄하게 이해하도록 노력해야겠다.

댓글남기기

참고