백준 2775번 - 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

 

 

a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 합만큼 사람들을 데려와 살아야 한다.

0층의 i호에는 i명이 산다.

 

문제의 의미는 다음 그림과 같다.

 

 

문제의 특징은 다음 그림과 같다.

예를 들어 1층의 2호에는 0층의 2호와 1층의 1호를 합한 수랑 같고

                 1층의 3호에는 0층의 3호와 1층의 2호를 합한 수랑 같다.

 

●그리하여 각 층의 호수별 사람 수를 2차원 배열로 나타내면 [ i ][ j ] = [ i-1 ][ j ]+[ i ][ j-1 ] 로 표현할 수 있다.

● 그리고 각 층의 1호는 그 전 층의 1호까지만 더하므로 모두 1명으로 공통점을 가진다. 

 

 

코드

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
	       Scanner sc = new Scanner(System.in);
	       
	       int apt[][] = new int[15][15];
	       
	       for(int i=1;i<15;i++)
	       {
           	   apt[0][i]=i;
	    	   apt[i][1]=1;
	       }
	       
	       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 = sc.nextInt();
	       for(int i=0;i<T;i++)
	       {
	    	   int k = sc.nextInt();
	           int n = sc.nextInt();
	           System.out.println(apt[k][n]);
	       }
	 }
}