백준 17626번 바로가기

나의 풀이

# 입력
import sys
n = int(sys.stdin.readline().strip())
squares = [i**2 for i in range(1,int(n**0.5)+1)]
queue = [n]
count = 0

# 처리 - bfs 활용
while len(queue) > 0:
  count += 1
  temp = set()
  for q in queue:
    for s in squares:
      if q < s:
        break
      temp.add(q-s)
  if 0 in queue:
    break
  queue = list(temp)
print(count-1)

고수의 풀이

dp = [50001 for i in range(n + 1)]
dp[0] = 0
for i in range(1, n + 1):
    for j in range(1, i + 1):
        val = j * j
        if val > i:
            break
        dp[i] = min(dp[i], dp[i - val] + 1)
print(dp[n])

출처

CODE REVIEW

  1. 처음에는 제곱수들을 역순으로 배열해서 차례대로 빼면 되겠지 생각했지만, 그게 최선의 수가 아니라는걸 깨달았다…
  2. bfs을 응용해서 n에서 0까지 top2bottom 방식으로 알고리즘을 구상했다.
    • BFS(너비 우선 탐색) 방식이 층별로 내려가는 식이라 과정이 유사하다는 점에서 착안했다.
  3. dp로는 도저히 풀어내는 방법을 모르겠어서 다른 사람의 풀이를 참고했다. 짧고 깔끔하게 잘 짰구만…👍👍
    • min(dp[i], dp[i-val]+1) 발상이 쉽지 않다. 허허