[BOJ, Python] 1699번_제곱수의 합

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기

백준 1699번

1차 코드(실패)

import sys
input = lambda: sys.stdin.readline().rstrip()
import math

N = int(input())
dp = [int(1e9)]*(N+1) # 1~N의 제곱수 항 최소 개수를 표현할 리스트
for i in range(1, int(math.sqrt(N))+1):
    dp[i**2] = 1

# 10을 만드는 최소항은 3^2(9) + 1^2
# 11을 만드는 경우 11보다 작은 수 중 가장 큰 제곱수를 빼고 그 수를 만드는 경우를 더해주면 된다.
for i in range(2, N+1):
    if dp[i] == 1:
        continue

    dp[i] = min(dp[i],
                1+dp[i-int(math.sqrt(i))**2])

print(dp[N])

현재 코드의 문제점
현재 코드는 N보다 작은 수 중 가장 큰 제곱수(M)을 N에서 빼고 그 뺀 수의 제곱수 최소항 갯수+1을 해서 제곱수 최소항의 갯수를 구하는 방식이다.
그러나 허점이 존재한다.

예를 들어, N이 14458인 경우 현재의 방식으로 하면 N-M=58이고, 58의 최소항의 갯수는 2이다. 그러므로 결과가 2+1=3이 나온다. 하지만 83^2+87^2=14458 이기에 N=14458의 최소항의 갯수는 2이다.
즉, 현재 코드는 정확한 최소항의 갯수를 찾지 못한다.

개선 방향
우선 N-M의 최소항의 갯수+1 공식부터 잘못됐다.
메모리를 신경쓰지 않는다면 가장 간단한 방법은 1~N의 제곱근(존재하는 경우) 범위에 존재하는 모든 제곱수를 N에서 빼고 그 수의 최소항의 갯수+1의 경우의 수를 모두 탐색하는 것이다.

2차 코드(성공)

import sys
input = lambda: sys.stdin.readline().rstrip()
import math

N = int(input())
dp = [int(1e9)]*(N+1) # 1~N의 제곱수 항 최소 개수를 표현할 리스트
for i in range(1, int(math.sqrt(N))+1):
    dp[i**2] = 1

for i in range(2, N+1):
    if dp[i] == 1:
        continue

    for j in range(int(math.sqrt(i)), 0, -1):
        dp[i] = min(dp[i],
                1+dp[i-j**2])

print(dp[N])

결과

코드는 성공했지만 많은 메모리 사용률과 높은 시간 복잡도를 해결하는 더 좋은 방법이 존재할 것 같다고 생각해서 다른 사람의 코드를 참고해서 다시 코드를 짜봤다.

최종 코드

import sys
input = lambda: sys.stdin.readline().rstrip()
import math

N = int(input())
dp = [int(1e9)]*(N+1) # 1~N의 제곱수 항 최소 개수를 표현할 리스트
for i in range(1, int(math.sqrt(N))+1):
    dp[i**2] = 1

for i in range(2, N+1):
    if dp[i] == 1:
        continue

    for j in range(int(math.sqrt(i)), 0, -1):
        if dp[i] > 1+dp[i-j**2]:
            dp[i] = 1+dp[i-j**2]

print(dp[N])

크게 변경된 부분은 없고, if dp[i] > 1+dp[i-j**2]: 기존 min으로 최소항의 갯수를 구하던 방식에서 if문으로 먼저 검증을 하는 방식으로 변경했다. 기존 방식은 모든 경우의 수에 대해서 min함수를 사용했는데 이처럼 if문으로 검증을 해준다면 min 함수를 사용하지 않고 dp 리스트가 변경되는 횟수를 감소시킬 수 있다.

결과