백준 2133 오답풀이

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

난이도: 골드4

 

해당 문제는 DP 문제로 생각보다 생각해야할 문제들이 많은 문제였다.

 

최초에 생각한 방식은 dp[6]이면 dp[4]와 dp[2]를 곱하고 둘의 순서가 바뀔 수 있으므로 2를 곱하면 될줄 알았다.

하지만 dp[4] 안에는 dp[2] dp[2]의 배열이 있기 때문에 중복되는 값이 존재한다는 점이었다.

 

따라서 dp[4]에만 있는 모양을 따로 빼기로 마음 먹었다. 모든 dp에는 나누어 떨어지지 않는 모양이 2개 존재한다.

 

따라서 dp[i-2] * dp[2]를 한 뒤 dp[i]에 나눠 떨어지지 않는 2가지 경우만 * 2를 해줬다 + dp[i]에만 존재하는 2개

 

결과적으로 아래와 같은 점화식을 세웠다

dp[i] = (dp[i - 2] + 2) * dp[2] + 2;

 

하지만 간과한게 있었다. 그것을 찾는데 시간이 오래 걸렸다.

dp[i-4], dp[4]에만 존재하는 모양 처럼 dp[2]가 아닌 다른 값이 포함된 모양은 현재 수식에선 추가되지 않은 상태인 것이다.

 

왜 생각을 못했을까...ㅠ

이전 dp문제와 달리 O(N^2)으로 계산되는 dp문제에 익숙하지 않은 dp문제였다.

 

따라서 dp[2]로 끝나는 값은 경우의 수가 3개 나머지는 경우의 수가 2개가 존재한다.

따라서 다음과 같이 점화식을 세웠다

 

dp[i] = dp[i - 2] * 3;
for (int j = i - 4; j > 0; j = j - 2) {
	dp[i] += dp[j] * 2;
}
dp[i] += 2;

 

맨윗줄은 dp[2]로 끝나는 경우의 수

나머지는 dp[j]에서 나눠 떨어지지 않은 모양(2)만 곱한다.

마지막은 dp[i]에서 나눠 떨어지지 않은 모양을 더한다.

 

 

전체 코드

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 + 2];

        dp[2] = 3;

        if (N < 4) {
            System.out.println(dp[N]);
            return;
        }
        dp[4] = 11;

        for (int i = 6; i < N + 1; i = i + 2) {

            dp[i] = dp[i - 2] * 3;
            for (int j = i - 4; j > 0; j = j - 2) {
                dp[i] += dp[j] * 2;
            }
            dp[i] += 2;
        }

        System.out.println(dp[N]);
    }
}