BOJ [Silver II] 제곱수의 합 - 1699

문제 링크

분류

다이나믹 프로그래밍(dp), 수학(math)

문제 설명

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 $11=3^2+1^2+1^2$(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 $11=2^2+2^2+1^2+1^2+1^2$(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

입출력 예

입력	7	1	4	11	13
출력	4	1	1	3	2

아이디어

i	1	2	3	4	5	6	7	8	9	10	11	12
i	$1^2$	$1^2+1$	$1^2+2$	$2^2$	$2^2+1$	$2^2+2$	$2^2+3$	$2^2+4$	$3^2$	$3^2+1$	$3^2+2$	$3^2+3$
d	1	1+1=2	1+2=3	1	1+1	1+2	1+3	1+1	1	1+1	1+2	1+3

• i = i의 직전 제곱수(i랑 가장 가깝게 작은 제곱수) + a라고 했을 때

  d = 1(=d[직전 제곱수]) + d[a] 이 규칙이라고 생각함

  이거를 식으로 구현하는 게 어려워서 다른 사람 풀이를 살짝 봤음 ㅜㅜ

• 직전 제곱수를 어떻게 찾을까 했는데,

  어쨌든 i를 제곱수의 합으로 나타낼 때의 항의 개수는

  d[i보다 작은 제곱수 k] + d[i-k] = 1 + d[i-k]로 나타낼 수 있고, 그 중에서 최솟값을 찾으면 되는 것이므로

  i보다 작은 수 j에 대해서 $\rm{j^2}$이 i보다 작을 동안 위의 점화식으로 d[i]를 구해서 min()으로 갱신

• 심지어 직전 제곱수일 때가 최솟값인 건 아님 !!!!!

  반례) $43^2$

  직전 제곱수가 $6^2$이고 이때 36+7이 되므로 d[$43^2$]은 5이지만,
  항의 개수 최솟값은 $5^2+3^2+3^2$일 때인 3임

  코드가 알아서 min으로 찾아줘서 맞았던 것뿐 ^^ ..

  아무튼 자기보다 작은 제곱수를 가지고 나타낸다고 생각했으니 대강 맞게 생각한 걸로 합리화해보기로 ..~~ ;;

풀이 코드: 시간 초과 → 맞았습니다

코드 1

n = int(input())
d = [0] * 100001
for i in range(1,n+1):
    d[i] = i   # 1^2으로 i를 만들 때의 개수(최댓값)
    for j in range(1, i):
        if j**2 > i:
            break
        d[i] = min(d[i], 1 + d[i - j**2])
print(d[n])

• 모든 i에 대해서 1만 가지고 i를 만들 때의 항의 개수인 i를 d[i]의 초기값으로 설정해줘야 함

• python3로 제출하면 시간 초과, pypy3로 제출하면 시간이 조금 (많이) 걸리지만 시간 초과는 안 남

  → min() 함수 때문

코드 2

n = int(input())
d = [0] * 100001
for i in range(1,n+1):
    d[i] = i   # 1^2으로 i를 만들 때의 개수(최댓값)
    for j in range(1, i):
        if j**2 > i:
            break
        if d[i] > 1 + d[i - j**2]:
            d[i] = 1 + d[i - j**2]  # 제곱수에 대한 값만 체크해서 갱신
print(d[n])

• min을 쓰지 않고 제곱수에 대한 값만 체크해서 갱신

• 이렇게 하면 python3도 시간 초과는 안 나지만 내 노트북에서는 채점 시간 오래 걸리긴 함 (그리고 vscode로는 얘가 미세하게 더 오래 걸린다..?)

다른 사람 코드

n = int(input())
d = [0] * 100001
sqrt = [i*i for i in range(1, int(n**0.5)+1)]  # 제곱수만 저장
for i in range(1,n+1):
    temp = []
    for j in sqrt:
        if j > i:
            break
        temp.append(d[i-j] + 1)
    d[i] = min(temp)
print(d[n])

• 먼저 [i*i for i in range(1, int(n**0.5)+1)]으로 n보다 작은 제곱수만 저장

  참고) i가 제곱수인지 판별하려면 math.sqrt(i)**2 == i 또는 (i**0.5)**2 == i 사용 가능

• 이 코드로 하면 각 제곱수로 나타내는 합마다의 항의 개수를 temp로 저장한 다음에 한 번만 min()을 하는 거라 시간이 덜 걸리는 것 같다..?

• vscode로 시간 찍어보면 입력 188일 때 위에 풀이 코드는 1, 2 둘 다 0.008 정도로 나오는데 이 코드는 0.003 정도!

---

암튼.. 구현이 어렵다
점화식 찾는 과정은 생각보다 재밌고 빨리 생각날 때도 많은데 인덱스 자체를 숫자로 생각하고 .. 갱신해줄 때 이중for문을 써야 하는지 뭐 이런 것들이 딱 바로 감이 오지는 않는다 ㅜㅜ
그리고 일단 고민하는 시간이 쪼끔 짧은 것 같아서 매 문제마다 조금만 더 집중하고 매달려보기로 .. !!