DP 문제
https://www.acmicpc.net/problem/1699
특정수를 제곱수의 합으로 나타낼 때, 그 항의 최소 개수를 구하는 문제이다.
즉 12 를 제곱수(1, 4, 9, 16, ...)의 합으로 구하는 방법은 아래와 같이 여러개가 존재한다.
1) 9 + 1 + 1 + 1 (4항)
2) 4 + 4 + 4 (3항)
3) 4 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 (9항)
즉, 12 를 표현하는 항의 최소 개수는 3항 임을 알 수 있다.
여기서 조심해야 할 점은, 사용할 수 있는 제곱근 중 가장 큰 수 ( = 9) 를 사용하는 1번 방법이 항상 좋은 것은 아니다.
그렇기 때문에, dp를 이용하여 풀어나간다.
dp 배열은 i 값을 제곱근의 합으로 나타냈을 때 가장 최소값을 가진다.
**dp 결과 값 : [0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
** 계산 순서
dp[1] 는 다음 값 중에 최소값을 갖는다.
1. 1제곱근(1)을 포함하는 경우 - 0 를 구하는 최소항 값에 + 1 한 값 = 1
dp[2] 는 다음 값 중에 최소값을 갖는다.
1. 1제곱근(1)을 포함하는 경우 - 1 를 구하는 최소항 값에 + 1 한 값 = 2
dp[3] 는 다음 값 중에 최소값을 갖는다.
1. 1제곱근(1)을 포함하는 경우 - 2 를 구하는 최소항 값에 + 1 한 값 = 3
dp[4] 는 다음 값 중에 최소값을 갖는다.
1. 1제곱근(1)을 포함하는 경우 - 3 를 구하는 최소항 값에 + 1 한 값 = 4
2. 2제곱근(4)을 포함하는 경우 - 0 를 구하는 최소항 값에 + 1 한 값 = 1
dp[5] 는 다음 값 중에 최소값을 갖는다.
1. 1제곱근(1)을 포함하는 경우 - 4 를 구하는 최소항 값에 + 1 한 값 = 2
2. 2제곱근(4)을 포함하는 경우 - 1 를 구하는 최소항 값에 + 1 한 값 = 2
dp[6] 는 다음 값 중에 최소값을 갖는다.
1. 1제곱근(1)을 포함하는 경우 - 5 를 구하는 최소항 값에 + 1 한 값 = 3
2. 2제곱근(4)을 포함하는 경우 - 2 를 구하는 최소항 값에 + 1 한 값 = 3
dp[7] 는 다음 값 중에 최소값을 갖는다.
1. 1제곱근(1)을 포함하는 경우 - 6 를 구하는 최소항 값에 + 1 한 값 = 4
2. 2제곱근(4)을 포함하는 경우 - 3 를 구하는 최소항 값에 + 1 한 값 = 4
dp[8] 는 다음 값 중에 최소값을 갖는다.
1. 1제곱근(1)을 포함하는 경우 - 7 를 구하는 최소항 값에 + 1 한 값 = 5
2. 2제곱근(4)을 포함하는 경우 - 4 를 구하는 최소항 값에 + 1 한 값 = 2
dp[9] 는 다음 값 중에 최소값을 갖는다.
1. 1제곱근(1)을 포함하는 경우 - 8 를 구하는 최소항 값에 + 1 한 값 = 3
2. 2제곱근(4)을 포함하는 경우 - 5 를 구하는 최소항 값에 + 1 한 값 = 3
3. 3제곱근(9)을 포함하는 경우 - 0 를 구하는 최소항 값에 + 1 한 값 = 1
dp[10] 는 다음 값 중에 최소값을 갖는다.
1. 1제곱근(1)을 포함하는 경우 - 9 를 구하는 최소항 값에 + 1 한 값 = 2
2. 2제곱근(4)을 포함하는 경우 - 6 를 구하는 최소항 값에 + 1 한 값 = 4
3. 3제곱근(9)을 포함하는 경우 - 1 를 구하는 최소항 값에 + 1 한 값 = 2
dp[11] 는 다음 값 중에 최소값을 갖는다.
1. 1제곱근(1)을 포함하는 경우 - 10 를 구하는 최소항 값에 + 1 한 값 = 3
2. 2제곱근(4)을 포함하는 경우 - 7 를 구하는 최소항 값에 + 1 한 값 = 5
3. 3제곱근(9)을 포함하는 경우 - 2 를 구하는 최소항 값에 + 1 한 값 = 3
dp[12] 는 다음 값 중에 최소값을 갖는다.
1. 1제곱근(1)을 포함하는 경우 - 11 를 구하는 최소항 값에 + 1 한 값 = 4
2. 2제곱근(4)을 포함하는 경우 - 8 를 구하는 최소항 값에 + 1 한 값 = 3
3. 3제곱근(9)을 포함하는 경우 - 3 를 구하는 최소항 값에 + 1 한 값 = 4
|
public class BOJ1699 { public static void main(String[] args) throws Exception { System.setIn(new FileInputStream("src/input.txt")); BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int dp[] = new int[N+1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0;
for(int i=1; i<=N; i++) { for(int j=1; j<=(int)Math.sqrt(i); j++) { dp[i] = Math.min(dp[i], dp[i - j*j] + 1); } } System.out.println(dp[N]); } } |
댓글