https://www.acmicpc.net/problem/1699
1699번: 제곱수의 합
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
import java.util.Scanner;
public class Main {
public static int n;
public static int[] arr;
public static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
dp = new int[n + 2];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
System.out.println(dp[n]);
}
}
|
cs |
18번째 줄 처럼 dp[i]=i로 초기화시켜준다. <--정말 중요
dp[2]=Math.min(dp[2],dp[2-1]+1) 즉 min(2,2)이므로 2
dp[3]=Math.min(dp[3],dp[3-1]+1) 즉 min(3,3)이므로 3
dp[4]는 i가 1일 때
Math.min(dp[4],dp[4-1]+1) => min(4,4) 이므로dp[4]=4
i가 2일때
Math.min(dp[4],dp[4-4]+1) =>min(4,1) 이므로 dp[4]=1이다.
dp[4]는 2의 제곱 한개만으로 만들 수 있기 때문에
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
위의 코드를 통해 제곱수 판별이 된 것을 알 수 있다.
문제를 풀면서 틀린부분
dp[i]=Math.min(dp[i],dp[i-j]+1)의 점화식을 생각해봤지만, 제곱수를 어떻게 다뤄야할지 도저히 감이 안왔다. 그래서 아래 링크에 있는 글을 봤는데,
https://www.acmicpc.net/board/view/13407
글 읽기 - 문제 1699 질문
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
답글을 보면 동전교환 알고리즘을 이용해서 풀어보라고 해서 동전교환 알고리즘을 찾아보았다.
https://withhamit.tistory.com/333
동전 교환(CC: Coin Change)
동전 교환(CC: Coin Change)은 다이나믹 알고리즘 중 하나입니다. CC는 동전의 종류들로 특정 금액을 만드는 경우의 수를 구하는 알고리즘입니다. 예를 들어서 1원, 2원, 5원, 10원 4가지 종류의 동전으
withhamit.tistory.com
--> 위 블로그 글이 설명을 잘 해주셨다.
d[i][j] = d[i-1][j] (0 <= j < cost[i])
= d[i][j-cost[i]] + d[i-1][j]
[알고리즘] Dynamic Programming (동적 계획법)
알고리즘의 꽃(이라고 생각합니다) 동적 계획법! 흔히 줄여서 DP라고 부르죠. 저는 개인적으로 이게 제일 어렵습니다 ㅠㅠ 그래서 오늘 한 번 뿌셔보려고 합니다 ** 이번 파트는 코드그라운드의 C
do-rang.tistory.com
이 글도 보면서 참고해봤다!
'알고리즘 > DP' 카테고리의 다른 글
| [java 백준] 실버 3/9461번 파도반 수열 (0) | 2021.08.10 |
|---|---|
| [java 백준] 실버 1/ 11052번 카드 구매하기 (0) | 2021.08.10 |
| [DP기초] 필요한 동전의 최소개수 구하기 (0) | 2021.08.06 |
| [DP기초] 계단오르기 (0) | 2021.08.06 |
| [java 백준] 실버 2/ 11055번 가장 큰 증가 부분 수열 (0) | 2021.08.05 |
댓글