[백준] 1699번:제곱수의 합 (Java 자바)

[백준] 1699번:제곱수의 합 (Java 자바)

반응형

문제

https://www.acmicpc.net/problem/1699

풀이 및 소스코드

처음에는 아래와 같이 생각했다.

n의 가장 가까운 제곱수 하나와 n에서 제곱수의 값을 뺀 수의 제곱수의 개수를 더하면 된다 ! 라고!

dp[10] 일 때, 10의 가장 가까운 제곱 수인 3^2 하나와 10-9 = 1인 dp[1]의 값을 더하면 될 것이라고 생각했다.

하지만 틀렸습니다 라는 결과가 나왔다. ㅜㅜ

또 다시 한 번 생각해봤다.

dp[10] = dp[1]+dp[9] = 2

= dp[2]+dp[8] = 4

= dp[3]+dp[7] = 7

= dp[4]+dp[6] = 4

= dp[5]+dp[5] = 4 의 최소값인 2가 정답이라는 것이 보였다.

위의 방법을 코드로 나타내면 아래와 같다 !

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] dp = new int[n+1]; dp[1] = 1; for(int i=2;i<=n;i++) { dp[i] = 10001; for(int j=1;j<=i/2;j++) { if(j*j==i) { dp[i] = 1; break; } dp[i] = Math.min(dp[i], dp[j]+dp[i-j]); } } System.out.println(dp[n]); } }

반응형

from http://jainn.tistory.com/274 by ccl(A) rewrite - 2021-09-20 23:01:56