백준 2775 Java

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

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다”
는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라.
단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

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

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

제한
1 ≤ k, n ≤ 14

 

이번 문제는 이전 문제보다 제약 조건과 문제를 잘
읽어보지 않는다면 많이 헤메일것이다... 제약조건이 있다는걸
보지못해서 꽤나 고민하였다.
 
일단 이 문제의 제약조건부터 살펴보자 1 <= k, n <= 14
1보다 크거나 같고 14보다 작거나 작아야한다.
즉, 14층까지만 있다는 것이다! 문제를 보면 0층부터 존재한다고 하니
0 ~ 14층이 존재 총 15층이 존재하는 것이다.
 
이 문제를 풀때에는 14층까지라는 제약이 있기에 모든 층, 호수에 살아야할 사람들의
숫자를 모두 채워넣고 값만 꺼내주는 식으로 문제를 풀것이다.
이러면 의문이 들수도 있다 k, n을 입력받고 찾아야 하는곳까지만 계산하면되지
왜 14층에 14호실까지 모든 값을 채워넣느냐라는 의문이 들수도 있을것이다.
이 문제를 풀때에 이차원 배열을 이용할건데 테스트케이스만큼 반복문을 돌려 값을 계속 구한다면
반복문이 한번 돌아갈때마다 원하는 호실까지의 모든 값을 계속 구하는 일이 벌어진다
그러면 굉장이 성능이 떨어지는 프로그램이 될것이다 그래서
모든 방의 값을 채워넣고 그 안에서 필요한 값만 꺼내오는 식으로 만들어준다.
 
1. 0층,0호실 ~ 14층,14호실까지 존재하기에 2중배열의 home의 크기를
[15][15]로 값을 준다.
     
2. 문제를 볼때에 각 층은 1호실부터 시작한다고 되어있다.
반복문을 이용하여 (i = 0; i < home.length; ++i) 인 반복문을 이용하여
home[0][i] = i  0층의 값을 순서대로 1, 2, 3....으로 초기화하여주고
(i의 초기값은 0이다! 1호실부터 존재한다 이 부분을 했갈리지 말자.)
home[i][1] = 1 각 층의 호실의 값을 1로 초기화하여준다.
     
3. 다음으로는 이중반복문을 살펴보자
바깥쪽 반복문은 0층은 이미다 초기화 되어있음으로 1층부터 14층까지만 구하면된다.
(int i = 1; i < 15; ++i)
안쪽 반복문은 1호실도 1로 초기화되있음으로 2호부터 14호까지만 구하면된다.
(int j = 2; j < 15; ++j)
     
home[i][j] = home[i][j-1] + home[i-1][j];
바로 앞호실 인원수 + 바로 아래층 호실 인원수 = 원하는 호실에 살아야할 인원수
이차원 배열의 모든 값을 초기화 시켜준다.
   
4. 이차원 배열과 이중 반복문을 통하여
이차원 배열안에 모든 값을 넣어뒀으니
원하는 값을 꺼내어서 출력하기만 하면된다!
이때에 주의할점은 평소StringTokenizer을 이용하여 문자열을 공백단위로
분리하여 사용하였지만 문제를 보면
각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다
라고 되어있다. 한줄씩 입력받아야 된다고한다 사소한 부분이지만 주의하도록 하자