[백준/JAVA] 2775 : 부녀회장이 될테야 ( 기본 수학 1 )

문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데,

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

는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때,

주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라.

단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다

출력

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

 

예제입력	예제출력
2 1 3 2 3	6 10

 

4층	1호 1명	2호 6명	3호 21명	4호 56명
3층	1호 1명	2호 5명	3호 15명	4호 35명
2층	1호 1명	2호 4명	3호 10명	4호 20명
1층	1호 1명	2호 3명	3호 6명	4호 10명
0층	1호 1명	2호 2명	3호 3명	4호 4명

2층의 3호에는 10명이사는데 

왼쪽 2호의 4명  아래층의 6명을 합치면 2층의3호는 10명이된다

이 구조까지는 이해했는데 도저히 이걸 전체배열을 다 초기화시켜두고 구해야하는건지

이전 문제들처럼 간단한 공식이 있는건지 고민고민하다가 어떻게 구현해야할지 감이 잡히지않아서 결국 구글링을 했다..

 

✅ 다른분의 풀이

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args)throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        
        int[][] intArr = new int[15][15];
        
        for(int i=0;i<intArr.length;i++){
            intArr[i][1]=1;
            intArr[0][i]=i;
        }
        for(int i=1;i<15;i++){
            for(int j=2;j<15;j++){
                intArr[i][j] = intArr[i][j-1]+intArr[i-1][j];
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<tc;i++){
            int k = Integer.parseInt(br.readLine());
            int n = Integer.parseInt(br.readLine());
            sb.append(intArr[k][n]).append("\n");
        }
        System.out.print(sb);
    }
}

✅ 우선 아파트 전체를 2차원배열로 만들었다.

그리고 각 1호에는 모두 1을 0층의 1~14호까지는 1씩증가시키며 값을 할당했다.

x	1
x	1
x	1
0	1	2	3

첫for문에서 이렇게 까지만 만들어둔것이다.

다음 for문에서  [i][j] = [i][j-1] + [i-1][j]

 

❗ 이렇게 구현하는거였구나..

	for(int i=1;i<15;i++){
            for(int j=2;j<15;j++){
                intArr[i][j] = intArr[i][j-1]+intArr[i-1][j];
            }
        }

[i][j-1]   [1][1] = 1층의 1호는 1

[i-1][j]   [0][2] = 0층의 2호는 2

[i][j] 1층의 2호는 1+2 = 3

이런식으로 14층 14호까지 전체에 해당값을 할당시켜주고

이렇게 만들어진 이차원배열에서 문제에서 주어진 k와 n을 넣어 출력시키면 된다.

 

이렇게 푸는 문제는 전체탐색 이라고 하는것같은데

구현을 어떻게 할지 감이 잡히지않던것도 있었고 ,시간초과가 나지않을까 싶어 전체를 구현해볼 생각은 안해봤는데

컴퓨터는 생각보다 빨랐고, 나는 생각만큼 미련했다

 

 

-출처

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