[JAVA] 백준 2775번 부녀회장이 될테야 : 이차원 배열

 

2775번: 부녀회장이 될테야

 

1. 문제 추상화

 

k층 n호의 사람의 수를 구하기 위해, k-1층의 1호 ~ n호까지의 사람의 합을 구하라.

 

2. 제약조건

 

▷ 시간 제한 : 1초

▷ 0 <= k, n <= 14

 

3. 알고리즘 

 

문제이해를 위해 간단히 표를 그린다.

 

	1호	2호	3호
3층	1	5	15
2층	1	4	10
1층	1	3	6
0층	1	2	3

 

3층 3호의 사람 수는 15명이다.

- 3층 3호의 사람 수 = 2층 1호 + 2층 2호 + 2층 3호

그러나 표를 보면 알 수 있듯이, 3층 3호의 사람 수는 3층 2호 + 2층 3호와 같다. 

 

고로, k층 n호의 사람 수는 k층 n-1호와 k-1층 n호의 사람 수 합과 같다. 

 

[ 순서 ] 

 

1. 0층의 사람의 수는 제시되었다. 

2. k와 n의 범위가 크지 않고 시간제한도 1초이다. 

3. 고로, 반복문을 통해 이차원배열을 초기화할 시간이 충분하다.

4. k와 n을 인덱스로 하는 이차원 배열을 생성하여 반복문을 통해 각 층의 호실의 값을 ( k층 n-1호 + k-1층 n호 )으로 구한다.

5. 입력받은 k와 n 인덱스가 가리키는 배열값을 출력한다.

 

 

개인적으로 나는 문제를 어렵게 접근했다. 문제를 보자마자 이차원배열을 떠올렸으나 반복문이 아닌 수식을 통해 문제를 풀고 싶었다. 그러나 제약조건을 보면 범위가 크지않고 시간제한도 널널하므로 반복문으로 충분히 풀 수 있는 문제이다. 가장 효율적인 방법을 찾으려 하지말고 가장 적합한 방법을 찾으려 노력하자.

 

4. 코드

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int[][] apart = new int[15][15];
		
		for(int i=0; i<15; i++) {
			apart[0][i] = i; // 0층 초기화
			apart[i][1] = 1; // 1호는 모두 1이다.
		}
		
		int layer = 0; // 층
		int roomNum = 0; // 호실
		
        // 층은 1층부터 호는 2호부터 초기화 시작
		for(layer = 1; layer<apart.length; layer++) {
			for(roomNum=2; roomNum<apart[layer].length;roomNum++) {
				apart[layer][roomNum] = apart[layer][roomNum-1] + apart[layer-1][roomNum]; // 규칙		
			}
		}
		
		int testcase = sc.nextInt();
		
		for(int i=0; i<testcase; i++) {
			layer = sc.nextInt();
			roomNum = sc.nextInt();
			System.out.println(apart[layer][roomNum]);
		}
	}

}