[DP] 백준 1699. 제곱수의 합

 

 

바텀업으로 배열을 채우고, 인덱스 n에 해당하는 값을 출력하는 식으로 품

d의 기본 배열을 각 인덱스로 채우는 게 다른 DP문제랑 다른 점이었고, 

( 1**2로만 더한 횟수가 최대이므로, 3 = 1**2 + 1**2 + 1**2 , 3에 대해 최대 횟수가 3임 )

 

이중 반복문, 제곱근까지는 생각했는데, 이걸 식으로 구현하는 게 어려웠다.

뺄셈으로 해결하신 분의 코드를 참고했다.

11을 예시로 원리를 설명해보자면, 11은 제곱의 항들로 표현되는 가짓수들의 일부는 이렇다.

11 = 1**2 + 1**2 + ...

11 = 2**2 + 2**2 + 1**1 + 1**1 + 1** 1

11 = 3**2 + 1**2 + 1**2 (최소 횟수)

어떤 자연수 N에 대해, N=1부터 시작하면서 N보다 작은 제곱수를 가장 작은 것부터 뺀다.

d[11] = min (d[11], d[11 - 1의 제곱] +1 )

d[11] = min (d[11], d[11 - 2의 제곱] +1 )

d[11] = min (d[11], d[11 - 3의 제곱] +1 )

 

14의 예시라면,

14 = 1**2 + 1**2 + ...

14 = 2**2 + 2**2 + 1**1 + 1**1 + 1** 1 

14 = 3**2 + 2**2 + 1**2 (최소 횟수)

어떤 자연수 N에 대해, N=1부터 시작하면서 N보다 작은 제곱수를 가장 작은 것부터 뺀다.

d[14] = min (d[14], d[14 - 1의 제곱] +1 )

d[14] = min (d[14], d[14 - 2의 제곱] +1 )

d[14] = min (d[14], d[14 - 3의 제곱] +1 )

 

* 이해가 어려웠던 부분

14의 예시에서, 3번 째 줄까지 되면, d[5] + 1 

d[5] 는 2**2 +1  즉, 2회로 2의 제곱이 포함된 계산으로 최소 횟수가 보장되어 있음.

 

# 시간초과 + 틀린코드
n = int(input())
d = list(i for i in range(n+1))

for x in range(1,n+1):
    y = 1
    while y*y <= x:
        y+=1
        d[x] = min(d[x], d[x-y*y]+ 1)


print(d[n])

 

뺄셈을 쓰는 게 진짜... 신박했다.

으아 포기하지 말자

 

 

1try : 위 코드대로 쓰면, 원리는 맞는데 딱 한 줄 때문에 틀린다.

2try, 3try : python3 랑 input 내장함수 그대로 썼더니 시간초과 뜬다.

4try : pypy + readline 정답 (아래코드)

 

import sys
input = sys.stdin.readline
n = int(input())
d = list(_ for _ in range(n+1))

for x in range(1,n+1):
    y = 1
    while y*y <= x:
        d[x] = min(d[x], d[x-y*y]+ 1)
        y+=1


print(d[n])

참고

https://chanhuiseok.github.io/posts/baek-10/