백준 (BOJ) 2705 팰린드롬 파티션 java dp

 

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

2705번: 팰린드롬 파티션

 

수를 나열한 후 살펴봐도 처음 아이디어를 얻기가 쉽지 않았던 문제

 

팰린드롬 파티션은 양쪽 파티션 합이 짝수일 때만 발생한다는 특징이 있다.

 

< 1의 경우 >

1

 

< 2의 경우 >

1 1
 2

 

< 3의 경우 >
1 1 1
  3

 

< 4의 경우 >

1 1 1 1
 1 2 1 
  2 2  
   4

 

< 8의 경우 >

1 1 1 1 1 1 1 1   ( (8-0)/2 == 4 )
  1 2 1 1 2 1      ( (8-0)/2 == 4 )
 1 1 1 2 1 1 1     ( (8-2)/2 == 3 )
      3 2 3          ( (8-2)/2 == 3 ) 
     2 2 2 2        ( (8-0)/2 == 4 )
    1 1 4 1 1       ( 2 )
      2 4 2          ( 2 )
       4 4            ( (8-0)/2 == 4 )
      1 6 1          ( 1 )
        8             ( dp[0] )

 

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));

        // N 최대 1000
        int[] dp = new int[1001];
        int diff;

        for(int i=1; i<1001; ++i){
            dp[i] = 1;
            for(int j=0; j<i; ++j){ // 짝수/홀수 두 경우이므로 0, 1 모두 필요
                diff = i-j;
                if((diff & 1) != 1) { // 홀수 아닐 떄만
                    dp[i] += dp[diff >> 1];
                }
            }
        }

        int T, N;
        T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int t=0; t<T; ++t){
            N = Integer.parseInt(br.readLine());
            sb.append(dp[N]).append("\n");
        }
        System.out.print(sb);

    }
}

 

비트로 (0000...0001)인 1과 특정 정수를 & 연산을 사용해서 홀짝 판별을 쉽게 할 수 있다.