[종만북] POLY - 폴리오미노 (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

문제 : aoj-POLY

 

 

풀이

  문제에서 제시된 규칙은 결국, 세로야 어떻든 가로로 선을 그었을 때 빈 곳이 있으면 안되고 또 전부 붙어있어야한다는 의미가 된다.

 

  따라서 n개를 행 1개~행 n개 에 걸쳐 각 행에 몇 개씩 배치할 것인지로 바꿔서 생각하면 된다.

그리고 2개의 행을 봤을 때, 두 행에 대해 만들 수 있는 경우의 수는 '행1의 블록 수 + 행2의 블록 수 - 1' 이 된다.

예를들어 각 행에 3개씩 배치했을 경우

 

  나올 수 있는 경우의 수는 3+3-1 = 5 이다. 아래 경우들과 같다.

 

  따라서 각 행별로 현재 남은 블록의 수를 '1개부터 남은 블록의 수'로 배치하면서 위에서 얘기한 경우의 수를 바로 직전 행의 블록수와 함께 계산해보면 된다. 

private void solution() throws Exception {
    int n = Integer.parseInt(br.readLine());

    long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += bf(n-i, i);
    }
    sb.append(sum%MOD).append('\n');
}

private long bf(int remain, int bf) {
    if (remain == 0) {
        return 1;
    }

    long result = 0l;
    for (int i = 1; i <= remain; i++) {
        long tmp = bf+i-1;
        tmp *= bf(remain-i, i);
        tmp %= MOD;
        result += tmp;
        result %= MOD;
    }

    return result;
}

 

  다만 위의 방식은 완전탐색을 진행한 경우로, 이 경우엔 시간초과가 나게 된다. 따라서 memoization으로 시간을 줄여볼 수 있다. 결국 경우의 수를 판단하는 기준은 '현재 남은 블록 수'와 '이전 행의 블록 수' 이므로, memoization 배열에 그 둘을 기준으로 결과 구한건 넣어두고 이미 계산한 적 있다면 사용해준다.

private void solution() throws Exception {
    int n = Integer.parseInt(br.readLine());
    memoization = new long[n+1][n+1];
    long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += bf(n-i, i);
    }
    sb.append(sum%MOD).append('\n');
}

private long bf(int remain, int bf) {
    if (memoization[remain][bf] != 0) {
        return memoization[remain][bf];
    }

    if (remain == 0) {
        return 1;
    }

    long result = 0l;
    for (int i = 1; i <= remain; i++) {
        long tmp = bf+i-1;
        tmp *= bf(remain-i, i);
        tmp %= MOD;
        result += tmp;
        result %= MOD;
    }

    return memoization[remain][bf] = result;
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static final long MOD = 10000000;
    long[][] memoization;

    public static void main(String[] args) throws Exception {
        int c = Integer.parseInt(br.readLine());
        while (c-->0) new Main().solution();
        System.out.print(sb);
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        memoization = new long[n+1][n+1];
        long sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += bf(n-i, i);
        }
        sb.append(sum%MOD).append('\n');
    }

    private long bf(int remain, int bf) {
        if (memoization[remain][bf] != 0) {
            return memoization[remain][bf];
        }

        if (remain == 0) {
            return 1;
        }

        long result = 0l;
        for (int i = 1; i <= remain; i++) {
            long tmp = bf+i-1;
            tmp *= bf(remain-i, i);
            tmp %= MOD;
            result += tmp;
            result %= MOD;
        }

        return memoization[remain][bf] = result;
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.