백준 1699 파이썬

 

 

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

 

 

오답 코드

 

테스트 케이스는 모두 맞췄길래 정답인줄 착각했다.

from math import sqrt

N = int(input())

n = N
count = 0
while N > 0:
    if int(sqrt(n)) == sqrt(n):
        N -= n
        count += 1
        n = N
    else:
        n -= 1

print(count)

 

반례는 12 를 입력할 때인데, 위 코드에선 4가 출력되지만, 정답은 3이다.

2^2 + 2^2 + 2^2 = 12가 되는 것인데, 오답 코드에서는 3^2 + 1^2 + 1^2 + 1^2 로 인해 4개의 수가 더해져 4가 출력되어 오답이 된다. 

이런 오답이 발생하는 원인은, N을 1씩 줄여가면서 제곱근을 구했기 때문이다. 다시 말해 큰 수부터 제곱수를 구했기 때문인데, 12같은 반례 케이스가 존재하기 때문에 이런식의 접근으로는 답에 도달할 수 없다. 

 

 

 

정답 코드

N = int(input())

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:
            break
        if dp[i] > dp[i - j * j] + 1:
            dp[i] = dp[i - j * j] + 1
print(dp[N])

 

dp 라는 배열을 만든다. 이 배열의 초기 내부 값은 각 인덱스와 동일한 값을 나타낸다.

N 이라는 타겟 넘버의 제곱수를 바로 구하는 것이 아닌, 

N 보다 작은 수 (i) 의 제곱수를 먼저 구하면서 N 까지 결과를 업데이트 하는 방법이라고 이해하면 되겠다.

 

정답 코드를 조금 리팩토링 할 수도 있다.

N = int(input())

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:
            break
        dp[i] = min(dp[i], dp[i - j * j] + 1)    
        # if dp[i] > dp[i - j * j] + 1:
        #    dp[i] = dp[i - j * j] + 1
print(dp[N])