https://www.acmicpc.net/problem/1699
1699번: 제곱수의 합
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다
www.acmicpc.net
정말 단순하게도 '제곱수들을 N번째 숫자까지 모두 저장해놓고 큰 수부터 빼면 구해지지 않을까?'라고 생각했다.
하지만 곧 반례를 찾았고, 이미 위와같은 생각에 사로잡혀 다른 방법이 도저히 떠오르지 않았다.
심지어 백준님의 강의로 해설을 듣고 나서도
대체 이것이 어떻게 구현된다는 말인지 아직까지도 이해가 안 되고 있다.......
대충 50% 정도의 현 이해력으로 정리를 해보자면,
초기 dp에 저장되는 배열은 1~n까지이며
이중 for문을 돌면서 제곱수가 현재의 수보다 크다면 넘기고
현재의 수보다 제곱수가 작다면, 현재의 수 - 제곱수를 하여 그 값에 대한 dp값을 가져온다.
이때 제곱수를 빼고 난 값의 dp값을 가져왔으므로, +1을 해주어 빼준 제곱수의 경우를 더해준다.
이렇게 for문을 다 돌고 나면,
dp배열의 n번째 수, 즉 입력받은 수의 결과가 저장되므로 dp[n]을 출력해주면 정답!
n = int(input())
dp = [ i for i 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문제를 풀어야 하는데... 많이 부족하다는 것을 느낀다.
'알고리즘 > Python' 카테고리의 다른 글
[백준/Python] 9461 파도반 수열 (0) | 2022.01.22 |
---|---|
[백준/Python] 2133 타일 채우기 (0) | 2022.01.22 |
[백준/Python] 2579 계단 오르기 (0) | 2022.01.18 |
[백준/Python] 1912 연속합 (0) | 2022.01.18 |
[백준/Python] 11054 가장 긴 바이토닉 부분 수열 (0) | 2022.01.18 |