BOJ 2775 - 부녀회장이 될테야

문제

아파트에서 k층 n호에 사는 사람 수는 (k-1)층 1호부터 n호까지의 합이다. 0층 i호에는 i명이 산다. k와 n이 주어질 때 거주자 수를 구하라.

입력

테스트 케이스 수 T, 각 케이스에 k와 n이 주어진다.

출력

각 케이스마다 k층 n호의 거주자 수를 출력한다.

예제

입력	출력
`2` `1` `3` `2` `3`	`6` `10`

풀이

2차원 DP 테이블을 미리 구성하여 각 층과 호수의 거주자 수를 계산한다.

0층 i호에는 i명을 초기화한다
각 층의 1호에는 1명을 초기화한다
APT[i][j] = APT[i][j-1] + APT[i-1][j] 점화식으로 채운다
각 쿼리에 대해 테이블에서 O(1)로 답을 조회한다

핵심 아이디어: 점화식이 누적합 형태이므로 왼쪽 값과 아래층 값을 더하면 된다. 최대 크기(14x14)가 작아 전체 테이블을 미리 계산한다.

코드

package day549;
 
import java.io.*;
 
public class Day520BOJ2775부녀회장 {
  public static int[][] APT = new int[15][15];
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
 
    for (int i = 0; i < 15; i++) {
      APT[i][1] = 1;
      APT[0][i] = i;
    }
 
    for (int i = 1; i < 15; i++) {
      for (int j = 2; j < 15; j++) {
        APT[i][j] = APT[i][j - 1] + APT[i - 1][j];
      }
    }
 
    int T = Integer.parseInt(br.readLine());
 
    for (int i = 0; i < T; i++) {
      int k = Integer.parseInt(br.readLine());
      int n = Integer.parseInt(br.readLine());
      sb.append(APT[k][n]).append('\n');
    }
    System.out.println(sb);
  }
}

복잡도

시간: O(K * N) - 전처리, 쿼리는 O(1)
공간: O(K * N)

문제