[백준 알고리즘][자바] 2775번 : 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

안녕하세요. 이번 포스팅은 백준알고리즘 2775번 부녀회장이 될테야입니다.

특이한 아파트가 하나 있습니다. 이 아파트에 거주할려면 다음과 같은 조건을 만족 시켜야합니다.

• k층 n호에 살려면 자신의 아래층(k-1)의 1호부터 n호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다.
• 단 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

예제를 살펴보도록 하겠습니다.

첫번째 예제는 1층의 3호입니다. 그럼 자신의 아래층인 0층의 1호부터 3호까지의 사람의 수만큼 데려와 살아야 합니다.

• 0층 1호 -> 1명
• 0층 2호 -> 2명
• 0층 3호 -> 3명

총 6명으로 출력과 같네요!

두번째 예제는 2층의 3호입니다. 그럼 자신의 아래층인 1층의 1호부터 3호까지의 사람의 수만큼 데려와 살아야 합니다.

• 1층 1호 -> 0층 1호 -> 1명
• 1층 2호 -> 0층 1호 + 0층 2호 -> 3명
• 1층 3호 -> 0층 1호 + 0층 2호 + 0층 3호 -> 6명

총 10명으로 출력과 같습니다.

그렇다면 k층의 n호에는 몇명이 살고 있을까요?

• (k-1)의 1호 + (k-1)의 2호 + ... + (k-1)의 n호

이 공식을 기억하며 아래와 같이 표를 구성하여 살펴보도록 하겠습니다.

우선 0층에 n호에는 n명이 살고있습니다.

1	2	3	4	5	6	7	8

또한 k층에 1호에는 모두 1명이 살수밖에 없습니다.

1
1
1	2	3	4	5	6	7	8

그다음 1층부터 채우보겠습니다.

1
1	3	6	10
1	2	3	4	5	6	7	8

여기서 1층의 5호를 채우게될텐데 1층의 5호는 공식에 따라 0층 1호 + 0층 2호 + ... 0층 5호 입니다.

그런데 1층의 4호가 0층 1호 + 0층 2호 + 0층 3호 + 0층 4호이기 때문에 

1층의 4호에서 0층의 5호만 더해주면 1층의 5호를 구할수 있습니다.

1
1	3	6	10	10 + 5
1	2	3	4	5	6	7	8

이러한 알고리즘에 의해 표를 2차원배열(14 X 14)로 구성하게되면 k와 n이 주어졌을 때 값을 출력할 수 있습니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine()); // T만큼 테스트 진행
		int[][] apart = new int[15][15]; // [k][n]
		
		for(int i = 0 ; i < 15 ; i++) {
			apart[i][1] = 1; // k층 1호는 모두 1명이다
			apart[0][i] = i; // 0층 1호부터 14호까지는 모두 1명이다
		}
		
		for(int k = 1 ; k < 15 ; k++) { // 1층부터 14층 까지 반복
			for( int n = 2 ; n < 15 ; n++) { // 2호부터 14호까지 반복
				apart[k][n] = apart[k][n-1] + apart[k-1][n]; // 공식대입
			}
		}
		
		for(int i = 0 ; i < T; i++) {
			
			int K = Integer.parseInt(br.readLine()); // 아파트 층 수
			int N = Integer.parseInt(br.readLine()); // 아파트 호 수
			
			bw.write(apart[K][N] + "\n");
		}

		br.close();
		bw.flush();
		bw.close();
	}
}