[BOJ] 15569 - 블록 1

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

BOJ - 블록 1

문제 유형: 다이나믹 프로그래밍

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 256MB

 

문제

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

 

입력

첫 번째 줄에 N과 M이 입력된다. (1 ≤ N ≤ 10^2, 1 ≤ M ≤ 10^4)

 

출력

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

 

풀이

dp[i][j] = i x j의 타일을 구성하는 경우의 수로 한다.

 

보통의 경우는 a x n짜리(a < n) 타일을 세로로 나열하여 구성하는 식을 생각하면 된다.그러나, n x n이상부터는, 회전을 고려하여야 한다. 여기부터는 회전이 가능하기 때문이다.

 

base case로, dp[0][n] = dp[1][n] = dp[n][1] = 1가지이다.

먼저, i <= n부터 고려하자.

dp[i][n] = sum of (dp[i-j][n]) for j in 1 ... i이다.

그리고, 대칭이므로 dp[i][n] = dp[n][i]이다.

 

그리고, n x n은 가로로 눕힌 경우의 수들도 고려해야 한다.

dp[n][n]에 두 배를 곱하고, n x n자체는 중복이므로 1을 뺀다.

이 연산을 취하기 전에, 변수에 dp[n][n]을 담아둔다.

 

이제, i > n일때는,

j < n인경우는 이전처럼 이어붙이면 되지만, j = n인경우, bnr을 곱해서 회전 가능한 n x n블록을 고려한다.

 

답은 dp[n][m]이다.

 

코드

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD int = 1999

var reader *bufio.Reader
var writer *bufio.Writer

var n, m int

func main() {
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	fmt.Fscan(reader, &n, &m)

	dp := make([][]int, n+1)
	mx := max(n, m)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, mx+1)
	}

	dp[0][n] = 1
	dp[1][n] = 1
	dp[n][1] = 1
	for i := 2; i <= n; i++ {
		for j := 1; j <= i; j++ {
			dp[i][n] += dp[i-j][n]
		}
		dp[i][n] %= MOD
		dp[n][i] = dp[i][n]
	}

	bnr := dp[n][n]
	dp[n][n] = ((dp[n][n] * 2) - 1) % MOD
	for i := n + 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if j == n {
				dp[n][i] += dp[n][i-j] * bnr
			} else {
				dp[n][i] += dp[n][i-j]
			}
		}
		dp[n][i] %= MOD
	}

	fmt.Fprintln(writer, dp[n][m])
}