백준 알고리즘 2410번: 2의 멱수의 합

문제 정보

---

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

 

 

문제 파악

---

문제 조건

1 <= N <= 1,000,000

답이 커질 수 있으므로 1,000,000,000 으로 나눈 나머지를 출력할 것

 

문제 내용

어떤 자연수 N을 입력했을 때, N을 2의 멱수의 합으로 나타내는 경우의 수를 구하여라

여기서 2의 멱수란 2^k 로 표현되는 자연수를 의미 (1, 2, 4, 8, 16 ...)

 

 

풀이

---

생각했던 내용

 /**
         * n=1
         * 1
         *
         * n=2
         * 1 1
         * 2
         *
         * n=3
         * 1 1 1
         * 2 1
         *
         * n=4
         * 1 1 1 1
         * 2 1 1
         * 2 2
         * 4
         *
         * n=5
         * 1 1 1 1 1
         * 2 1 1 1
         * 2 2 1
         * 4 1
         *
         * n=6
         * 1 1 1 1 1 1
         * 2 1 1 1 1
         * 2 2 1 1
         * 4 1 1
         *
         * 2 2 2
         * 4 2
         *
         * n=7
         * 1 1 1 1 1 1 1
         * 2 1 1 1 1 1
         * 2 2 1 1 1
         * 4 1 1 1
         *
         * 2 2 2 1
         * 4 2 1
         *
         * n=8
         * 1 1 1 1 1 1 1 1
         * 2 1 1 1 1 1 1
         * 2 2 1 1 1 1
         * 4 1 1 1 1
         * 2 2 2 1 1
         * 4 2 1 1
         *
         * 2 2 2 2
         * 4 2 2
         * 4 4
         * 8
         *
         *
         */

정리했던 N=1부터 8까지의 2의 멱수의 합으로 이루어진 경우의 수이다

여기서 쉽게 알수 있는 사실은 홀수일 때에는 이전 경우의 수와 똑같다는 것이다(단지 이전 경우의 수들 자체에 1을 더한 것임)

따라서 이를 만약 DP로 풀이하게 된다면, 점화식은 다음과 같다

(홀수일 경우) DP[i] = DP[i-1]

 

짝수일 경우에는 파악하기 조금 힘들 수도 있는데

* n=6
* 1 1 1 1 1 1
* 2 1 1 1 1
* 2 2 1 1
* 4 1 1
*
* 2 2 2
* 4 2

N=6일 때를 살펴보면, 먼저 위 4개의 줄은 이전 경우의 수(DP[5])와 동일하다(단지 +1을 했음)

아래 두 줄을 보면, 쉽게 파악이 되지 않을 수도 있지만 사실

 

* n=3
* 1 1 1
* 2 1

N=3일 때의 *2를 한 것이 N=6일 때의 아래 두 줄이 된다는 점을 발견할 수 있다

 

동일하게도, N=8일 때를 살펴보면

* n=8
* 1 1 1 1 1 1 1 1
* 2 1 1 1 1 1 1
* 2 2 1 1 1 1
* 4 1 1 1 1
* 2 2 2 1 1
* 4 2 1 1
*
* 2 2 2 2
* 4 2 2
* 4 4
* 8

위 6줄은 N=7일 때의 경우와 동일하다고 볼 수 있고,

 

아래 4줄의 경우는

* n=4
* 1 1 1 1
* 2 1 1
* 2 2
* 4

N=4일 때의 경우들에 *2를 한 것과 동일하다

 

따라서 위 점화식을 구성해 보면

if dp[i] % 2 == 0:
	dp[i] = dp[i-1] + dp[i/2]
else:
	dp[i] = dp[i-1]

다음과 같이 구성할 수 있다

 

코드

---

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 + 1];
        dp[1] = 1;
        if (N == 1) {
            System.out.println(1);
            return;
        }

        for (int i = 2; i <= N; i++) {
            dp[i] = (i % 2 == 0) ? (dp[i - 1] + dp[i / 2]) % 1_000_000_000 : dp[i - 1];
        }
        System.out.println(dp[N]);
    }
}

 

 

Source Code on GitHub

---