[백준 - 15569번] 블록 1 - Java

문제 링크

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

문제

티어: 골드 3
알고리즘: dp
여러 가지 블록들을 이용하여 직사각형 모양을 만들려고 한다. 우리에게는 1 × N 블록, 2 × N 블록, ..., N × N 블록이 무한하게 있다. 이 블록들을 사용하여 N × M 모양을 만들고 싶다. 만들 수 있는 총 방법의 수를 1999로 나눈 나머지를 구하여라.

입력

첫 번째 줄에 N과 M이 입력된다. (1 ≤ N ≤ 102, 1 ≤ M ≤ 104)

출력

총 가능한 경우의 수를 1999로 나눈 나머지를 출력한다.

풀이

N x M 모양을 만들기 위한 가능한 모든 경우의 수를 구해야 한다.

N이 4라고 한다면 블럭의 종류는

• 1 x 4
• 2 x 4
• 3 x 4
• 4 x 4
  이렇게 4개 존재한다.

2 x 4를 만들 수 있는 경우의 수를 보면 1 x 4를 활용해서 2 x 4를 만들 수 있다.
그래서 2개가 된다.

3 x 4 또한 1 x 4, 2 x 4를 활용해서 만들 수 있다. 그런데 이미 2 x 4를 만드는 경우의 수를 구했고, 그 경우에는 1 x 4 블록이 포함되었기 때문에 dp[2 x 4] 값을 활용하면 중복 탐색을 없앨 수 있다. (dp[2 x 4] -> dp[2][4])

다시 3 x 4를 보면 넣을 수 있는 블럭의 종류는 1 x 4, 2 x 4, 3 x 4가 된다.
1 x 4를 하나 넣는다면 dp[2 x 4]의 경우의 수가 존재하고
2 x 4를 하나 넣는다면 dp[1 x 4]의 경우의 수
3 x 4는 하나 존재한다.
그래서 dp[3 x 4]는 dp[2 x 4] + dp[1 x 4] + 1이라고 할 수 있다.

여기서 dp[4 x 4]를 구하는 경우는 좀 달라진다.
블록을 회전해서 넣는 경우도 있기 때문에 추가적으로 4 x 1, 4 x 2, 4 x 3 블록이 있다.

그래서 dp[4 x 4]는 (dp[3 x 4] + dp[2 x 4] + dp[1 x 4]) * 2 + 1이 된다. (회전한다고 해도 dp[2 x 4]나 dp[4 x 2]나 같은 값을 가짐)

N x N까지 구했다면 이후에 우리가 필요한 값은 N * M이다.
그래서 이번에는 가로의 길이를 늘려가며 경우의 수를 구해야 한다.

dp[4 x 5]는 경우의 수가 다음과 같다.

• 4 x 1 블록을 하나 넣는 경우 dp[4][4]
• 4 x 2 블록을 하나 넣는 경우 dp[4][3]
• 4 x 3 블록을 하나 넣는 경우 dp[4][2]
• 4 x 4 블록을 하나 넣고, dp[4][1]
  지금까지 우리는 회전한 블록만을 넣었기 때문에 회전하지 않은 블록을 포함한 경우도 더해 줘야 한다. 4 x 4는 회전하지 않은 블록들 1 x 4, 2 x 4, 3 x 4를 포함할 수 있는 영역을 가졌기 때문에 경우의 수의 dp[3 x 4] + dp[2 x 4] + dp[1 x 4]를 더해준다.
  그래서 4 x 4를 넣는 모든 경우의 수는 dp[4][1] * (1 + dp[3 x 4] + dp[2 x 4] + dp[1 x 4])가 된다.

이를 M까지 반복해주면 된다.

이 풀이의 시간 복잡도는 O(N * M)이다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 1999;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());
      
      int[][] dp = new int[N + 1][10000];
      dp[0][N] = 1; //자기자신
      dp[1][N] = 1;
      dp[N][1] = 1;
      for(int i=2; i<=N; i++) {
          for(int j=1; j<=i; j++) {
              dp[i][N] += dp[i - j][N];
          }
          dp[i][N] %= MOD;
          dp[N][i] = dp[i][N];
      }
      int bnr = dp[N][N] - 1;//N * N을 회전하지 않은 블록으로 채운 경우의 수 자기 자신 제외
      dp[N][N] = ((dp[N][N] * 2) - 1) % MOD;
      for(int i=N+1; i<=M; i++) {
          for(int j=1; j<=N; j++) {
              if(j == N) {
                  dp[N][i] += dp[N][i - j] * (1 + bnr);
              } else {
                  dp[N][i] += dp[N][i - j];
              }
          }
          dp[N][i] %= MOD;
      }
      System.out.println(dp[N][M]);
  }
}