백준 25345번
https://www.acmicpc.net/problem/25345

문제

---

루나와 리나는 타워 건설 게임을 하려고 한다. 타워 건설 게임은 $K$개의 타워를 사용하는 게임이고 루나는 이 게임을 세팅하려고 한다.

게임 세팅은 서로 다른 높이의 $N$개의 타워 중 $K$개를 선택해 원하는 순서로 일렬로 배치하는 것이다. 이때 앞과 뒤에서 바라볼 때 모든 타워가 최소 한 번은 보여야 한다. 즉, 어떤 타워에 대해서 그보다 높은 타워가 그 타워의 앞쪽과 뒤쪽에 모두 존재하면 안된다는 것이다.

게임 세팅을 하던 루나는 문득 게임을 세팅하는 방법이 얼마나 많을 지가 궁금해졌다. 루나를 도와서 게임 세팅을 하는 경우의 수를 구해보자.

생각하기

---

• 이항계수 -> $n$$C$$r$을 활용할 것
• 식 : $(k-1)$$2$ * $n$$C$$k$
• 조합의 개수를 구할 때, DP를 통해 구현할 것 memoization을 사용하자
  (일반 재귀로 구현할 경우 시간초과가 나게 된다 ($O$n2) )

이항 계수 참고
https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98

• 이항 계수의 항등식을 활용하기
  

• 파스칼의 삼각형
  
  파스칼의 삼각형을 2차원 배열로 DP를 통해 구현하면 $n$$C$$r$을 구할 수 있습니다.

동작

		for(int i=0; i<=N; i++) {
			memo[i][0] = 1;
			for(int j=1; j<=i; j++) {
				memo[i][j] = (memo[i-1][j-1] + memo[i-1][j]) % mod;
			}
		}

시간 복잡도를 고려하여 이항계수를 DP로 구현하였다. memoization 활용

		int comb = memo[N][K];
		for(int i=1; i<K; i++) comb = comb * 2 % mod;

이후 조합의 값 comb 변수에서 K-1의 제곱값 까지 곱해야 하기 때문에 반복문을 통해서
(k-1)^2의 값을 계산한다.

대회 당일 날 4시간 가까이 고민만 하다가 문제를 못풀어서 다음날 까지 고민하다가 다른 분들에게 도움을 청했는데, 다들 친절하게 알려주셨다. 그 분들이 이 글을 보실지는 모르겠지만, 정말 감사하다는 말을 하고싶다 feat.(슥삭, 회색 장어.. 많은 분들)

코드

---

Java

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

public class Main {
	private static final int mod = 1000000007;
	static int memo[][] = new int[2001][2001];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		DP(N);
		int comb = memo[N][K];
		for(int i=1; i<K; i++) comb = comb * 2 % mod;
		System.out.print(comb);
	} // End of main
	
	private static void DP(int N) {
		for(int i=0; i<=N; i++) {
			memo[i][0] = 1;
			for(int j=1; j<=i; j++) {
				memo[i][j] = (memo[i-1][j-1] + memo[i-1][j]) % mod;
			}
		}
	} // End of DP
} // End of Main class

Kotlin

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

private const val mod = 1000000007
private lateinit var memo : Array<IntArray>
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(br.readLine())
    var N = st.nextToken().toInt()
    var K = st.nextToken().toInt()
    memo = Array(2001){IntArray(2001)}

    DP(N)
    var comb = memo[N][K]
    for(i in 1 until K) comb = comb * 2 % mod
    print(comb)
} // End of main

private fun DP(N : Int) {
    for(i in 0..N) {
        memo[i][0] = 1
        for(j in 1..i) memo[i][j] = (memo[i-1][j-1] + memo[i-1][j]) % mod
    }
} // End of DP