백준 2775번[수학] 부녀회장이 될테야

---

1) 2차원 배열을 사용한 탐색으로 풀이

● 2차원 배열과 이중 for문을 이용해 몇 명이 사는지 계산해주고, 입력받은 k와 n을 배열에 대입해 출력했다.

● arr[0][i] = i을 통해 0층의 1 ~ 14 호까지 1 ~ 14 값을 넣어주고, arr[i][1] = 1 을 통해 몇 층이든 관계없이 한 명만 거주하고 있기

    때문에 1값을 넣어 초기화 시켜주었다.

● 몇 층에 관계없이 1 호에는 한 명만 거주한다라는 말은 즉, 값을 넣어줄 때 102호, 202호, 302호 ..(중략) 부터 찾아서 값을 넣어주면

    된다는 뜻이다.

● 따라서 이중 for문 (i=1, j=2)을 사용해 빈 값을 찾아 넣어준다.

  - "A층의 B호에 살기 위해선 자신의 아래 (A-1)층의 1호부터 B호까지 사람들의 수를 합한 것 만큼 살아야한다."라고 명시되어 있다.

  - 아래 표를 잘 보면, 몇 호에 몇 명이 사는지 구하기 위해 (자신 바로 아래 층의 사람 수)와 (자신 바로 왼쪽의 호수의 사람 수)를 더해주는

     것을 알 수 있다.

  - 따라서 arr[i][j] = arr[i-1][j] + arr[i][j-1]; 식을 사용하면 되는 것이다.

● 2차원 배열에 모든 값이 들어간 이후 testCase만큼 반복문을 돌려 k = 층, n = 호수를 배열에 넣고 값을 출력하면 끝!

 

4층	401호 (1명)	402호 (6명)	403호 (21명)	404호 (56명)
3층	301호 (1명)	302호 (5명)	303호 (15명)	304호 (35명)
2층	201호 (1명)	202호 (4명)	203호 (10명)	204호 (20명)
1층	101호 (1명)	102호 (3명)	103호 (6명)	104호 (10명)
0층	001호 (1명)	002호 (2명)	003호 (3명)	004호 (4명)
	1호	2호	3호	4호

 

import java.io.*;

public class Baek_2775 {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        
        // 2차원 배열 생성 [층][호] (1<=k,n<=14)
        int[][] arr = new int[15][15];              

        for (int i = 1; i < 15; i++) {
            arr[0][i] = i; // 0층의 i호의 사람 수는 i명
            arr[i][1] = 1; // i층의 1호의 사람 수는 1명
        }
        // 1층부터 탐색
        for (int i = 1; i < 15; i++) {
            // 2호부터 탐색
            for (int j = 2; j < 15; j++) {
                arr[i][j] = arr[i][j-1] + arr[i-1][j];
            }
        }

        for (int i = 0; i < testCase; i++) {
            int k = Integer.parseInt(br.readLine());    // 층수
            int n = Integer.parseInt(br.readLine());    // 호수
            System.out.println(arr[k][n]);
        }
    }
}