[백준] 2410번. 2의 멱수의 합(JAVA)

문제

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

---

풀이(32분)

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] dp = new int[n+1];
        dp[1]=1;
        if (n > 1) {
            dp[2] = 2; // n이 2 이상인 경우에만 dp[2] 초기화
        }
        for (int i =3; i <n+1; i++) {
            if(i%2==0) {
                dp[i]=(dp[i-1]+dp[i/2])%1000000000;
            }else {
                dp[i]=dp[i-1];
            }
        }
        System.out.println(dp[n]);
    }

}

 

일반적인 dp문제와 동일하게 직접 나열해 보며 경우를 찾았다.

 

하지만 생각보다 잘 되지 않았다.

그 이유는 아래와 같다.

1. 홀수인 경우 +1만 앞에 생기는 것이기 때문에 이 전 dp의 값을 복사한다. -> 여기는 쉬웠다.

 

2. 짝수인 경우 이전 dp의 값 +1 인 것과, -2일 때를 생각해야 한다.

-> 여기서 -2인 경우를 그대로 +해주면 중복되는 값이 생기는 문제가 발생했다.

예를 들어 6인 경우 1+1+2+2+2를 -1인 값에서 체크했지만 -2인 경우에도 2+1+1+2+2가 될 수 있는 것이다.

그래서 -1을 제외하고 어떤 것들이 추가되어야 하는지를 살펴보았다.

 

1+5(를 만들 수 있는 경우)를 제외하면, 2+2+2, 2+4를 카운트해야 했다. 이는 3을 만드는 경우인 1+1+1과, 1+2에 곱하기 2를 하는 것과 동일하다는 것을 알게 되었다.

 

따라서 위와 같은 최종적인 점화식이 나오게 되었다.