17626

날짜 : 2022. 12. 25

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
dp = [0, 1]

for i in range(2, n+1):
    t = int(1e9)  # 임의의 값
    j = 1
    while (j ** 2) <= i:
        t = min(t, dp[i - (j ** 2)])
        j += 1
    dp.append(t + 1)
print(dp[n])

 

 

풀이

- n을 입력받은 후 n보다 작은 수 중에서 제곱수를 구한다. (각 제곱수를 기준으로 더해서 n을 만든다고 생각하면 된다.)

- 그 수의 최솟값을 추출하여 해당 값(i)에서 차감한 후 리스트 dp에 1을 증가한 값으로 추가한다.

리스트 dp는 다음과 같이 나타난다.(인덱스 0부터 출력)

0 // 1 2 3 // 1 2 3 4 2 3 4 2 // 1 2 3 4 2 3 4 // 1 2 3 ....

 

예를들어 n이 32인 경우 n 이하의 제곱수 중 최댓값은 25이다.

그러면 32 - 25 = 7, 32 - 16 = 16, 32 - 9 = 23, 32 - 4 = 28, 32 - 1 = 31을 확인할 수 있다.

각각 dp[7], dp[16], dp[23], dp[28], dp[31]이 도출되는데 그 중 min을 갱신하기 때문에 dp[16]이 최솟값으로 나타난다.

dp[16] = dp[0] = 0 이기 때문에 1을 더해줌으로써 dp[32]를 설정한다.

 

- 이처럼 n까지 반복해서 진행한 후에 output 을 출력하면 된다.

 

 

알게된 점

- 맨 처음 group별로 분류한 다음 그 그룹에서의 순서를 통해 답을 찾으려 했는데 계속 오답이 나왔다.

- 그래서 결국 구글링을 했고 위와같은 풀이를 확인할 수 있었다.

- 특히나 내가 dp 개념이 많이 약하게 느껴지기 때문에 문제를 많이 풀어봄으로써 유형을 익히는 것이 중요하게 느껴진다.

 

 

참고 사이트

-