[백준 알고리즘] 1699번 제곱수의 합, 파이썬(python)
글 작성자: 망고좋아
반응형
1699, 제곱수의 합
📁 문제 출처
💡 생각
- 그 항의 최소 개수를 구하는 문제이다.
- n=11이라면 3^2밖에 사용하지 못한다. 그러면 dp에는 [0, 1, 4, 9] 이렇게 제곱수를 저장해주고 [::-1]해준 뒤 n -= arr[i]해주면서 결괏값을 +=1해 주는 아이디어를 떠올렸지만 틀렸다.
틀린 코드
n = int(input())
arr = [0]
for i in range(1, n):
if i ** 2 < n + 1:
arr.append(i ** 2)
else:
break
arr = arr[::-1]
cnt = 0
while True:
if n == 0:
break
for i in range(len(arr)-1):
if n >= arr[i]:
n -= arr[i]
cnt += 1
print(cnt)
- 무조건 큰 수의 제곱수들로만 나타내는 것이 정답이 아니다.
🛠 나의 코드
시간 초과
import sys
input = sys.stdin.readline
n = int(input())
dp = [0] * (n + 1)
for i in range(1, n+1):
dp[i] = i
for j in range(1, (i//2 +1)):
if (j * j) > i:
break
dp[i] = min(dp[i], dp[i - j * j] + 1)
print(dp[n])
- min함수 사용으로 인해 시간 초과
통과
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에는 1의 제곱으로 구한 개수를 저장한다.
dp[i - j * j] + 1
에서+1
을 해주는 이유는dp[4] = dp[4 - 2 * 2] + 1
=dp[0] + 1
=1
- dp[4]는 2^2이므로 최소항의 개수가 1이다. 따라서 dp[0]의 개수에서 +1을 해줘야 한다.
dp[i] > dp[i - j * j] + 1
은 말 그대로dp[i]
가dp[i - j * j] + 1
보다 크기 때문에 최소항의 개수가 아니다.- 따라서
dp[i - j * j] + 1
로 바꿔줘야 한다.
✔️ 배운 점 및 주의할 점
- 수학적 사고
- 다양한 DP유형의 문제 풀기
- 규칙을 찾기까지의 어려움
📌 참고한 코드
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 알고리즘] 18258번 큐 2, 파이썬(python) (0) | 2021.08.10 |
---|---|
[백준 알고리즘] 6198번 옥상 정원 꾸미기, 파이썬(python) (2) | 2021.08.10 |
[백준 알고리즘] 1463번 1로 만들기, 파이썬(python) (0) | 2021.08.03 |
[백준 알고리즘] 1406번 에디터, 파이썬(python) (0) | 2021.07.31 |
[백준 알고리즘] 1373번 2진수 8진수, 파이썬(python) (0) | 2021.07.31 |
댓글
이 글 공유하기
다른 글
-
[백준 알고리즘] 18258번 큐 2, 파이썬(python)
[백준 알고리즘] 18258번 큐 2, 파이썬(python)
2021.08.10 -
[백준 알고리즘] 6198번 옥상 정원 꾸미기, 파이썬(python)
[백준 알고리즘] 6198번 옥상 정원 꾸미기, 파이썬(python)
2021.08.10 -
[백준 알고리즘] 1463번 1로 만들기, 파이썬(python)
[백준 알고리즘] 1463번 1로 만들기, 파이썬(python)
2021.08.03 -
[백준 알고리즘] 1406번 에디터, 파이썬(python)
[백준 알고리즘] 1406번 에디터, 파이썬(python)
2021.07.31