팬린드롬 파티-션

팬린드롬 파티-션

 

백준 2705번 문제

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

 

 

 

1. 문제

 

 

 

2. 풀이

2.1 아이디어

임의의 수 n(n > 0을 만족하는 정수)을  a0 + x0 + a0 의 파티션으로 표현할 수 있다고 하자.

a0을 파티션으로 만들었을 때 a0 + x0 + a0가 재귀적 팰린드롬 파티션이 되려면 a0의 파티션이 재귀적 파티션이면 된다.

 

[재귀적 팰린드롬 파티션 예시 그_1]

 

임의의 수 n의 재귀적 팰린드롬 파티션의 개수를 D(n)이라고 하자.

임의의 수 n을 a0 + x0 + a0의 파티션 으로 표현하는 방법은 [n/2] 이다.([]는 가우스 기호를 의미)

 

[재귀적 팰린드롬 파티션 예시 그_2]

 

[재귀적 팰린드롬 파티션 예시 그_3]

 

a0 + x0 + a0의 재귀적 팰린드롬의 개수는 D(a0)이므로 다음과 같은 점화식이 성립한다.

 

D(n) = D(1) + D(2) + ... + D([n/2])

 

그런데 점화식의 가우스 기호의 특성상 홀수일때는 항이 늘어나지 않고 짝수일 때만 늘어난다.

 

[점화식 예시]

 

따라서 점화식을 다음과 같이 정리할 수 있다.

 

D(n) = D(n - 1) (n이 홀수 일 경우)

D(n) = D(n - 1) + D(n/2) (n이 짝수 일 경우)

 

2.2 점화식 코드

점화식으로 재귀적 팰린드롬 파티션을 구하는 메서드이다.

 

[initPalindrome]

public static void initPalindrome(int[] palindromeArr) {
    palindromeArr[1] = 1;

    for (int i = 2; i < palindromeArr.length; i++) {
        if (i % 2 == 0) {
            palindromeArr[i] = palindromeArr[i - 1] + palindromeArr[i / 2];
        } else {
            palindromeArr[i] = palindromeArr[i - 1];
        }
    }
}

 

 

 

3. 전체 코드

[전체 코드]

import java.io.*;

public class 팰린드롬_파티션_2705 {

    public static void initPalindrome(int[] palindromeArr) {
        palindromeArr[1] = 1;

        for (int i = 2; i < palindromeArr.length; i++) {
            if (i % 2 == 0) {
                palindromeArr[i] = palindromeArr[i - 1] + palindromeArr[i / 2];
            } else {
                palindromeArr[i] = palindromeArr[i - 1];
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] palindromeArr = new int[1001];
        initPalindrome(palindromeArr);

        int caseSize = Integer.parseInt(br.readLine());

        for (int i = 0; i < caseSize; i++) {
            int number = Integer.parseInt(br.readLine());
            bw.write(String.valueOf(palindromeArr[number]));
            bw.newLine();
        }

        bw.flush();
    }
}