[백준] 1301 - 비즈 공예(Java)

문제 파악

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

풀이

모든 상태를 해시맵에 담는 방법으로 풀이했더니, OOM이 발생했다 😇

N의 범위 [3,5]가 상당히 한정적이므로  다차원 배열을 선언해 상태를 저장하기로 결정했다.
(참고로 최대 개수인 5로 고정해 연산을 진행하였다.)
또 3개가 연속하면 안 되는 제약조건 때문에 [마지막에서 두 번째 구슬 종류][마지막 구슬 종류]도 DP 배열에 반영해야 한다.

그러므로 DP 배열은
[1번째 구슬 개수][2..][3..][4..][5번째 구슬 개수][마지막에서 두 번째 구슬 종류][마지막 구슬 종류]
로 7차원 배열을 가진다.

DP 배열만 잘 선언해주면, 나머지는 풀이가 그렇게 어렵지는 않다.

이미 계산한 상태(문제)의 결과를 저장해 두고, 같은 계산을 다시 하지 않도록 하는 기법인 DP의 기조에 근거하여

• 값이 있다면 리턴
• 값이 없다면 다음 참고 값을 연산하거나 불러 와 합산해 리턴

을 진행하도록 하자.

이를 코드에 녹여내면 다음과 같다.

코드

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

public class Main {
    static int beadColorCount;
    static int[] beadArr;
    static long[][][][][][][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        beadColorCount = Integer.parseInt(br.readLine()); // [3,5]
        beadArr = new int[5];
        for (int b = 0; b < beadColorCount; b++) {
            int count = Integer.parseInt(br.readLine());
            beadArr[b] = count;
        }
        int MAX = 12; // 각 구슬 수가 최대 12
        dp = new long[MAX][MAX][MAX][MAX][MAX][6][6];
        for (int a = 0; a < MAX; a++)
            for (int b = 0; b < MAX; b++)
                for (int c = 0; c < MAX; c++)
                    for (int d = 0; d < MAX; d++)
                        for (int e = 0; e < MAX; e++)
                            for (int l = 0; l < 6; l++)
                                for (int cnt = 0; cnt < 6; cnt++)
                                    dp[a][b][c][d][e][l][cnt] = -1;
        System.out.println(dfs(5, 5)); // 존재하지 않는 5번째 구슬로 호출
    }

	// last1 = 마지막 구슬의 종류, last2 = 마지막에서 두 번째 구슬의 종류
    static long dfs(int last1, int last2) {
        if (Arrays.stream(beadArr).sum() == 0L) return 1;
        long status = dp[beadArr[0]][beadArr[1]][beadArr[2]][beadArr[3]][beadArr[4]][last1][last2];
        if (status != -1)
            return status;
        long res = 0;
        for (int i = 0; i < beadColorCount; i++) {
            if (beadArr[i] == 0 || i == last1 || i == last2) continue;
            beadArr[i]--;
            res += dfs(i, last1);
            beadArr[i]++;
        }
        dp[beadArr[0]][beadArr[1]][beadArr[2]][beadArr[3]][beadArr[4]][last1][last2] = res;
        return res;
    }
}