https://www.acmicpc.net/problem/1699
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] dp = new int[n+1];
for(int i=1; i<=n; i++){
dp[i] = i;
}
for(int i=1; i<=n; 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]);
}
}
이문제는 정말 모르겠어서 다른 블로그들을 참고해서 이해했다.
예를 들어 n = 10이라고 하면,
dp[10] = dp[10-1*1], dp[10-2*2], dp[10-3*3]중 최솟값 + 1
로 표현할 수 있다.
그렇기 때문에 j*j가 i가 될때까지 이중 for문을 돌며 최솟값을 구한다.
참고
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=occidere&logNo=220792326120
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 1932번- 정수 삼각형 (0) | 2022.11.02 |
---|---|
[JAVA] 백준 1149번- RGB거리 (0) | 2022.11.02 |
[JAVA] 백준 2193번- 이친수 (0) | 2022.11.01 |
[JAVA] 백준 15988번- 1, 2, 3 더하기 3 (0) | 2022.10.31 |
[JAVA] 백준 10844번- 쉬운 계단 수 (0) | 2022.10.31 |