[백준] 2775번 : 부녀회장이 될테야 자바(JAVA) 풀이

문제

---

 

---

문제 탐색하기

• K : 층 수 
• N : 호 수

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

 

a 층 b 호 사람 수 = (a-1) 층 1호 + (a-1) 층 2호 + ... + (a-1) 층 b호 사람 수

 

주어진 정보대로 2차원 배열을 만들어서 아파트와 같은 구조를 만들면 아래와 같은 표가 완성된다.

5층
4층
3층
2층
1층
0층	1	2	3	4	5
	1호	2호	3호	4호	5호

 

예를 들어, 1층 3호에 사는 사람을 구한다고 하면 빨간색 박스의 합이 파란색 박스의 값이 되는 것을 알 수 있다. 

 

그런데 노란색 박스의 합은 보라색 박스와 같으므로 

파란색 박스 = 빨간색 박스 + 보라색 박스라고 볼 수 있다. 

 

따라서, a층 b호 사람 수 = (a-1) 층 b 호 + a 층 (b-1) 호 가 된다.

 

가능한 시간복잡도

입력 범위 ( 1 ≤ K , N ≤ 14)

 

K 층의 N 호 사람 수를 구할 때 까지 이차원 배열을 쌓아나가려면 O(K) * O(N) 번의 연산이 필요하다.  K와 N 모두 최대 14이므로 최대 연산수는 196이 된다.

 

---

코드 설계하기

• Testcase, K, N을 각각 입력받는다.
• 0층에 사는 사람의 수를 2차원 배열에 저장한다. 
• (a-1) 층 b 호 + a 층 (b-1) 호 규칙에 맞춰서 배열에 사람 수를 저장한다.
• 배열에 저장된 값을 출력한다.

---

풀이 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		int[][] people; // 아파트 거주민 수를 담을 배열
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine()); // TestCase
		
		for(int t=0;t<T;t++) {
			int k = Integer.parseInt(br.readLine()); // k 층수
			int n = Integer.parseInt(br.readLine()); // n 호
			
			people = new int[k+1][n+1];
			
			// 0층 i호에 i명이 사는 배열 생성
			for(int i=1;i<n+1;i++) {
				people[0][i] = i;
			}
			
			// k층 n호에 사는 배열 생성
			for(int i=1;i<k+1;i++) {
				for(int j=1;j<n+1;j++) {
					people[i][j] = people[i][j-1] + people[i-1][j];
				}
			}
			System.out.println(people[k][n]);
		}
	}
}