[백준] 1301번 - 비즈 공예 (Gold 3)

문제 링크

[백준] 1301번 - 비즈 공예 (Gold 3)

문제 설명

구슬의 가짓수 N과 각 종류의 구슬의 개수가 주어진다.
이 구슬들로 직선의 목걸이를 만들려고 하는데, 연속된 세개의 구슬은 모두 다른 색이어야 한다.
목걸이를 만들 수 있는 경우의 수를 구하시오.

정답 코드 및 설명

종류별로 사용된 구슬의 수와 마지막 구슬 두개가 정해져 있을 때 경우의 수가 몇 가지 가능한지를 구하면 된다.
N이 5 이하이므로 7차원 배열을 사용하면 쉽게 해결할 수 있다.
아래의 코드는 7차원 배열 대신 Map을 사용하여 top-down 방식으로 구현한 것이다.
Map의 키로는 종류별로 사용된 구슬의 수 및 마지막 구슬 두개가 저장된 객체가 들어간다.
이렇게 구현할 경우 구슬의 가짓수 N에 무관하게 문제를 풀 수 있다는 장점이 있다.
단점은 배열보다는 조금 더 느리다는 것이다. 해시를 계산하는 과정이 들어가기 때문이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Objects;

public class BOJ1301 {
    int n, sum;
    int[] color;
    HashMap<Count, Long> count = new HashMap<>();

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        color = new int[n];
        sum = 0;
        for (int i = 0; i < n; i++) {
            color[i] = Integer.parseInt(br.readLine());
            sum += color[i];
        }
    }

    class Count {
        int[] countColor;
        int secondToLast, last;

        Count(int[] countColor, int secondToLast, int last) {
            this.countColor = new int[n];
            this.countColor = countColor.clone();
            this.secondToLast = secondToLast;
            this.last = last;
        }

        public boolean equals(Object o) {
            if (!(o instanceof Count))
                return false;
            Count count = (Count) o;
            if (secondToLast != count.secondToLast) return false;
            if (last != count.last) return false;
            for (int i = 0; i < n; i++)
                if (countColor[i] != count.countColor[i]) return false;
            return true;
        }

        public int hashCode() {
            return Objects.hash(Arrays.hashCode(countColor), secondToLast, last);
        }
    }

    long DP(Count curr) { // top-down 방식의 DP
        if (count.get(curr) != null)
            return count.get(curr);
        int[] beforeCountColor = curr.countColor.clone();
        beforeCountColor[curr.last]--;
        long ans = 0;
        for (int k = 0; k < n; k++) { // 마지막에서 세번째 구슬이 k인 경우
            // 마지막에서 세번째 색이 k가 될 수 없는 경우(중복인 경우 또는 구슬 k를 다 쓴 경우)
            if (k == curr.last || k == curr.secondToLast || beforeCountColor[k] == 0) continue;
            Count before = new Count(beforeCountColor, k, curr.secondToLast);
            ans += DP(before);
        }
        count.put(curr, ans);
        return ans;
    }

    void initializeDP() {
        int[] countColor = new int[n];
        for (int i = 0; i < n; i++) {
            countColor[i]++;
            for (int j = 0; j < n; j++) {
                countColor[j]++;
                Count curr = new Count(countColor, i, j);
                if (i != j) count.put(curr, 1L);
                countColor[j]--;
            }
            countColor[i]--;
        }
    }

    void solution() throws IOException {
        input();
        initializeDP();
        long ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j == i) continue;
                Count curr = new Count(color, j, i);
                ans += DP(curr);
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) throws IOException {
        new BOJ1301().solution();
    }
}