https://www.acmicpc.net/problem/2775
문제
> 평소 반상회에 참석하는 것을 좋아하는 주희는
이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.
> 이 아파트에 거주를 하려면 조건이 있는데,
“a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는
계약 조항을 꼭 지키고 들어와야 한다.
> 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때,
주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라.
> 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.접근
어떤 값을 얻기 위해 다른 어떤 값들이 연계되어있으면 DP를 사용하는 문제다. 문제의 규칙을 볼때, 예를들어 3층의 4호를 알고 싶으면 2층의 1,2,3,4호를 전부 더해야한다.
3층의 5호는 2층의 1,2,3,4,5호를 전부 더해야한다. 이를통해 규칙을 축약할 수 있는데, 3층의 5호는 3층의 4호 + 2층 5호이다.
즉, dp(k)(n) = dp(k)(n-1) + dp(k-1)(n)이 된다.
문제해결
> 매 테스트 케이스마다 dp값을 새로 구하면 비효율적이므로
미리 0부터 14층, 1부터 14호까지의 집에대해 dp(15)(15)를 구한다.
> 1호실은 항상 1명만 살기 때문에 dp(i)(1)은 항상 1로 준다.
> 0층의 각 호실엔 각 호실 만큼의 사람이 있으므로 i가0일 때도 j로 초기값을 처리한다.
> 이제 초기 처리가 끝났고 앞서 구한 규칙을 적용해 14층 14호까지 모두 구한다.
> 각 테스트 케이스별로 k와 n을 입력받고 각각 dp(k)(n)을 출력한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main
{
//2775 부녀회장이 될테야
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int[][] dp = new int[15][15];
for(int i = 0; i < 15; i++)
{
dp[i][1] = 1;
for(int j = 2; j <= 14; j++)
{
if(i == 0)
{
dp[i][j] = j;
continue;
}
dp[i][j] = dp[i][j-1] + dp[i-1][j];
}
}
StringBuilder sb = new StringBuilder();
while(T-->0)
{
int k = Integer.parseInt(br.readLine());
int n = Integer.parseInt(br.readLine());
sb.append(dp[k][n]).append('\n');
}
System.out.print(sb);
}
}
후기
미리 dp를 전부 구할지 각각 특정 dp까지만 구할지 어떤게 더 효율적일까 고민했는데 예제상으론 몰라도 만약 매번 최악의 경우만 주면 미리 구하는게 더 효율적이므로 미리 구했다.
