😲 문제
출처
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.
주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.입력 7 출력 4
❗️ 문제 재정의
한 자연수를 어떤 제곱수들의 조합으로 표현하는 것이다.
최악을 한 번 가정해보자.
가장 최악은 해당 자연수가 1의 제곱으로만 이루어졌다는 것이다.
그렇다면 최선은 무엇일까
특정 자연수의 제곱으로만 이루어졌다는 것이되겠다.
ex) 4는 2의 제곱으로 제곱수 1개로 이루어져있다.
결국 특정 자연수가 어떤 제곱수로 이루어져있는지 알기위해서는
특정 제곱수와 그 나머지 수(이 또한 어떤 특정 제곱수의 합이다)로 이루어져있는지 확인해야한다. 결국 제곱수를 다 넣어보며 탐색하는 과정일 수 밖에 없다.
특정 제곱수라는 것은 아까의 예시대로 그 항의 개수는 1이라는 의미이다.
그럼 점화식을 세워보자
dp[i] = dp[i-j**2] + 1 중 가장 작은 값이다.
시작값은 어떤 것일까?
아까 말했든 최악의 값인 전부 1의 제곱으로만 이루어질 경우인 i 그 자체이다.
dp[i] = min(dp[i-j**2] + 1, d[i])로 세울 수 있겠다.
✔ 계획 수립
- 입력 받기
- 입력에 해당하는 개수만큼 d배열 초기화
- d[1]부터 d[n]까지 순차적으로 채워나가기
- d[i] = min(dp[i-j**2] + 1, d[i]) 이다.
👨🏻💻 문제 풀이
첫번째 풀이 - 시간초과
# 각 항이 있고 제곱수의 합으로 표현 가능하다.
# 각 제곱 수는 가장 큰 제곱수와 나머지로 이루어질 수 잇고
# 아닐 수도 잇다.
# 때문에 결국 전체 탐색이 필요하다.
n = int(input())
d = [0] * (n+1)
d[1] = 1
d[2] = 2
d[3] = 3
d[4] = 1
d[5] = 2
# 규칙이 보이는가?
# i 번째 수가 어떤 j*j와 i-j*j의 조합으로 이루어져 있다는 것.
for i in range(2,n+1):
j = 1
d[i] = i # 이 경우는 최악 조합을 가정한 값이다(전부 1로 이루어져 잇는 경우)
while j*j<=i: # 어떤 수와 어떤 수를 비교해야 하는가? 어떤 수 j 의 제곱의 항은 1개이다.
d[i] = min(d[i-j*j]+1, d[i])
j+=1
print(d[n])첫번째 풀이에서 시간초과가 발생했다. 내 이론상 무조건 완료가 되어야 하는데 말이다. 그렇다면 최적화 문제라고 생각해 필요 없는 부분을 지워봤다.
두번째 풀이 - 성공
# 각 항이 있고 제곱수의 합으로 표현 가능하다.
# 각 제곱 수는 가장 큰 제곱수와 나머지로 이루어질 수 잇고
# 아닐 수도 잇다.
# 때문에 결국 전체 탐색이 필요하다.
n = int(input())
d = [0] * (n+1)
d[1] = 1
# 규칙이 보이는가?
# i 번째 수가 어떤 j 번째 수와 i-j의 조합으로 이루어져 있다는 것.
for i in range(2,n+1):
j = 1
d[i] = i # 이 경우는 최악 조합을 가정한 값이다(전부 1로 이루어져 잇는 경우)
while j*j<=i: # 어떤 수와 어떤 수를 비교해야 하는가? 어떤 수 j 의 제곱의 항은 1개이다.
if d[i-j*j] + 1 < d[i]: # 여기가 변경 사항이다.
d[i] = d[i-j*j] + 1
j+=1
print(d[n])아무래도 매번 d[i]를 갱신하는 부분에서 시간초과가 발생한 듯 하여 해당 부분을 제거하고 if문으로 갱신 여부를 결정하게 했더니 성공하였다. 근데 아무리봐도 필요없는 부분이 더 보이는 듯 하여 더 최적화를 진행해보았다.
세번째 풀이 - 두번째 풀이에서 더 최적화
n = int(input()) # 입력
d = [i for i in range(n+1)] # 미리 각 d[i]에 최악의 수인 i로 초기화
squares = [i*i for i in range(n+1)] # 미리 제곱수를 만들어두어 비교 연산 시 다시 계산하는 과정을 없앰.
for i in range(n+1): # 각 자연수에 대한 제곱항이 몇 개인지 탐색
for square in squares: # 제곱항을 1부터 i보다 작은 수까지 어떤 조합인지 순차적 확인
if square > i: # i보다 크다면 종료
break
if d[i-square] + 1 < d[i]: # d[i]를 갱신하는 조건
d[i] = d[i-square] + 1
print(d[n])
위에서부터 3번째, 2번째, 1번째 풀이이다.
시간이 꽤나 유의미하게 줄어들은 것을 확인할 수 있었다.
😅 회고
처음에 접근 방식을 d[i]를 구할때 모든 제곱합의 조합을 생각하지 않고 가장 큰 제곱합과 나머지의 조합이 가장 적을 것이라고 생각했었다.
ex) 41은 36과 5의 조합이다. -> 정답은 41은 25와 16의 조합이라는 것이다.
접근 방식이 아예 잘못되어서 한참 헤매었다. 이후 맞는 접근 방식을 찾았지만 시간이 약간 오버되어 시간초과가 발생하여 최적화하는 과정을 거쳤다.
세 코드 전부 최악의 경우는 O(n * sqrt(n))이라는 것을 알 수 있다. 하지만 n이 커진다면 어느정도 유의미한 시간차이가 나는듯 싶다.
