백준 1301번: 비즈 공예

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

 

3~5개 색의 구슬들을 전부 연결했을 때, 임의의 연속된 3개의 구슬의 색깔이 전부 다르게 연결할 수 있는 경우의 수를 구하는 문제이다. 구슬의 색깔별로 구슬의 갯수가 주어지며 양 끝은 분리되어 있다.

 

이전에 선택했던 구슬의 색의 정보와 남아있는 색별 구슬의 갯수 상태가 필요하므로 dfs로 하면 편할 것이라고 생각했으며, 이러한 상태를 누적하여 모든 경우의 수를 구할 수 있는 dp가 시간 초과를 발생하지 않고 해결할 방법임을 떠올리게 되었다. dp에는 각 구슬의 색깔 별 남아있는 구슬의 수를, 마지막 2개는 직전과 그전에 선택했던 구슬의 색깔을 의미한다. 

dp = new long[board[0] + 1][board[1] + 1][board[2] + 1][board[3] + 1][board[4] + 1][6][6];

 

 

dfs에서 구슬 색깔 별 남아있는 구슬 갯수와 직전, 그 전에 선택했던 구슬의 색을 가지고 선택할 수 있는 색이 없으면 1을 반환하고, 이전에 이 경우의 수를 찾았다면, 이전에 찾았던 값을 반환한다. 구슬 색깔별로 순회하면서 이 색깔이 전에 쓰이지 않았으면서 남아 있다면 그 구슬을 선택하는 경우에 대해 dfs를 수행하여 경우의 수를 누적하여 dp에 저장 후, 반환한다.

private static long solve(int b1, int b2, int b3, int b4, int b5, int p1, int p2) {
    if (b1 == 0 && b2 == 0 && b3 == 0 && b4 == 0 && b5 == 0) {
        return 1;
    }
    if (dp[b1][b2][b3][b4][b5][p1][p2] != -1) {
        return dp[b1][b2][b3][b4][b5][p1][p2];
    }
    long count = 0;
    int[] currentBeads = {b1, b2, b3, b4, b5};
    
    for (int i = 0; i < 5; i++) {
        int color = i + 1;
        if (currentBeads[i] > 0 && color != p1 && color != p2) {
            int[] nextBeads = currentBeads.clone();
            nextBeads[i]--;
            
            count += solve(nextBeads[0], nextBeads[1], nextBeads[2], nextBeads[3], nextBeads[4], color, p1);
        }
    }
    
    return dp[b1][b2][b3][b4][b5][p1][p2] = count;
}

 

 

최종 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 비즈공예1301 {
    
    static long[][][][][][][] dp;
    static int[] board;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        board = new int[5];
        for (int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        
        dp = new long[board[0] + 1][board[1] + 1][board[2] + 1][board[3] + 1][board[4] + 1][6][6];
        for (long[][][][][][] a : dp) {
            for (long[][][][][] b : a) {
                for (long[][][][] c : b) {
                    for (long[][][] d : c) {
                        for (long[][] e : d) {
                            for (long[] f : e) {
                                Arrays.fill(f, -1);
                            }
                        }
                    }
                }
            }
        }
        System.out.print(solve(board[0], board[1], board[2], board[3], board[4], 0, 0));
    }
    
    private static long solve(int b1, int b2, int b3, int b4, int b5, int p1, int p2) {
        if (b1 == 0 && b2 == 0 && b3 == 0 && b4 == 0 && b5 == 0) {
            return 1;
        }
        if (dp[b1][b2][b3][b4][b5][p1][p2] != -1) {
            return dp[b1][b2][b3][b4][b5][p1][p2];
        }
        long count = 0;
        int[] currentBeads = {b1, b2, b3, b4, b5};
        
        for (int i = 0; i < 5; i++) {
            int color = i + 1;
            if (currentBeads[i] > 0 && color != p1 && color != p2) {
                int[] nextBeads = currentBeads.clone();
                nextBeads[i]--;
                
                count += solve(nextBeads[0], nextBeads[1], nextBeads[2], nextBeads[3], nextBeads[4], color, p1);
            }
        }
        
        return dp[b1][b2][b3][b4][b5][p1][p2] = count;
    }
}