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

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

2775번: 부녀회장이 될테야

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{

    public static int countPeople(int k, int n){
    	if(k==0) return n; // 0층일 경우 n명
        if(n==1) return 1; // 1호일 경우 사람의 수는 무조건 1명
        
        return (countPeople(k,n-1) + countPeople(k-1,n));
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        while(T-- >0){
            int k = Integer.parseInt(br.readLine()); // 층
            int n = Integer.parseInt(br.readLine()); // 호

            System.out.println(countPeople(k,n));
        }
    }
}

 

 

문제 이해는 바로 됐지만 코드로 구현하는게 어려웠다 ,,

그러다 간략하게 표를 그려서 해보니까 규칙을 발견했다.

 

	1호	2호	3호
3F	1	5	15
2F	1	4	10
1F	1	3	6
0F	1	2	3

 

k층 n호의 사람 수는 (k층 n-1호의 사람수) + (k-1층 n호의 사람 수)다.

0층일 경우, 사람수는 무조건 해당 호의 숫자이고, 1호일 경우 무조건 사람 수는 1이다.

 

 

이렇게 재귀로 풀었다. 

 

 

 

 

 

다른 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        final int SIZE = 15;

        int[][] house=new int[SIZE][SIZE];

        for(int i=0; i<SIZE; i++){
            house[i][1]=1; // 1호는 1명
            house[0][i]=i; // 0층은 i명
        }

        for(int i=1; i<SIZE; i++){ // 1층부터 14층
            for(int j=2; j<SIZE; j++){ // 2호부터 14호
                house[i][j]=house[i][j-1]+house[i-1][j];
            }
        }

        while(T-- >0){
            int k = Integer.parseInt(br.readLine()); // 층
            int n = Integer.parseInt(br.readLine()); // 호

            System.out.println(house[k][n]);
        }
    }
}

 

 

다른 풀이들을 보니 이렇게 2차원 배열으로 많이 푸는것 같다.