-
[백준 - 1699번] 제곱수의 합 - Java //Wello Horld//Algorithm/BOJ(Baekjoon Online Judge) 2019. 7. 15. 16:23
이번에는 백준 알고리즘의 1699번 문제 "제곱수의 합을" 풀어보도록 하자
이번문제에서 사용할 알고리즘은 다이나믹 프로그래밍이다. 또한, 어느정도의 수학적으로 접근법만 알고 있으면 쉬운 문제이다.
일단, 이 문제를 처음보고 아래 첨부한 것과 같이 반복문 안에다가 입력값 N을 루트를 때려버리고 그 값을 빼가면서 반복문을 돌린 횟수로 답을 구하는 알고리즘을 작성한 후 제출한 결과 틀렸다는 걸 알았는데,
import java.io.*; import java.util.*; public class sample { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int N = Integer.parseInt(br.readLine()); int cnt = 0; while(N != 0){ int temp = (int) Math.sqrt(N); N -= Math.pow(temp, 2); System.out.println(temp); cnt++; } bw.write(cnt + "\n"); bw.flush(); br.close(); bw.close(); } }
위 코드가 틀린 이유는 위의 코드로 N = 18일 때, 18 = 4^4 + 1^1 + 1^1 로 답이 3이 나온다. 하지만, 답은 18 = 3^2 + 3^2 이므로, 위의 코드는 이번 문제를 푸는데 적절하지 않다는 것을 알 수 있었다.
그래서, 이번 문제를 푸는데, 다이나믹 프로그래밍을 이용해서 문제를 풀었다. 일단, 입력값 N 은 (1 <= N <= 100,000) 이므로, 317의 제곱값(100,489)보다 작으므로, 아래와 같이 세팅했다.
int[] dp = new int[317 * 317 + 1];
또한, 입력값이 48일 때, 다이나믹 프로그래밍을 이용해서 문제를 풀려면, dp[32] + 1, dp[39] + 1, dp[44] + 1, dp[47] + 1 중에서 값이 가장 작은 것을 고르면 된다. 해서, helper라고하는 정수 배열을 [317 + 1] 만큼의 크기로 만들어서, 문제를 푸는데 도움을 줄 수 있도록 했다.
성공한 코드 전문은 아래와 같다.
import java.io.*; import java.util.*; public class sample { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int N = Integer.parseInt(br.readLine()); int[] dp = new int[317 * 317 + 1]; int[] helper = new int[317 + 1]; for(int i = 1; i <= 317; i++){ helper[i] = i * i; dp[i * i] = 1; } for(int i = 2; i <= N + 1; i++){ if(dp[i] != 0) continue; dp[i] = 317; for(int j = 1; 0 < i - helper[j]; j++){ dp[i] = Math.min(dp[i], dp[i - helper[j]] + 1); } } bw.write(dp[N] + "\n"); bw.flush(); br.close(); bw.close(); } }
'Algorithm > BOJ(Baekjoon Online Judge)' 카테고리의 다른 글
[백준 2869번] 달팽이는 올라가고 싶다 - Java //Wello Horld// (0) 2019.07.17 [백준 - 1946번] 신입사원 - Java //Wello Horld// (0) 2019.07.16 [백준 - 1049번] 기타줄 - Java //Wello Horld// (0) 2019.07.12 [백준 - 17298번] 오큰수 -Java //Wello Horld// (0) 2019.07.12 [백준 - 9461번] 파도반 수열 - Java //Wello Horld// (0) 2019.07.10