Java - [백준] 2775번 : 부녀회장이 될테야

1. 문제

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

2775번: 부녀회장이 될테야

• 입력 : 첫 번째 줄에 Test case의 수 T가 주어지며,  그다음부터 층수 k, 호수 n이 주어진다
• 출력 : 각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

---

2. 생각

본 문제는 크게 Recursion과 규칙성, 두 가지 경우로 풀 수 있다.  하지만, Recursion인 경우 모든 경우에 대해서 접근해야 하기 때문에 규칙성을 이용한 풀이보다 시간 면에서 상대적으로 떨어진다.

 

예를 들어 8층 11호(k=8, n=11)에 사는 거주민의 수를 구하는 것이 목표라면 

1. 7층 1호 ~ 7층 11호까지 거주민들의 수를 모두 더해야 할 것이다.
2. 7층에 사는 각각의 거주민들의 수를 알기 위해서는 1번 과정에 대해서 7층에 사는 집들에게 적용해야 할 것이다.
3. 위 과정을 8층, 7층, 6층 .... 1층까지 적용해야 할 것이며, 0층에 다다르면 i호에 사는 거주민들의 수를 가지고 다시 계산해야 할 것이다.

위 알고리즘을 보았을 때, 처음에는 8층 11호 거주민의 수를 구하는 문제에서 7층, 6층, ... 으로 점차 문제를 작게 쪼개게 되는데, 이는 Recursion의 특성이라 할 수 있다.

 

 

Q) Recursion의 Base case는 무엇인가?

- 8층 11호에 사는 거주민의 수를 구하기 위해서는 7층 1호 ~ 11호까지의 거주민 수를 알아야한다. 하지만, 7층에 사는 
  거주민 수를 알기 위해서는 6층에 사는 거주민 수를 알아야 한다. 즉, 각 층의 거주민들을 알기 위해서는 0층에 도달해야
  만 0층의 i호에 사는 거주민 수가 i명인 점을 이용하여 차례차례 계산할 수 있다.

- Base case : k==0 일때까지 Recursion

 

위 내용들을 바탕으로 하여 코드를 작성하면 아래와 같다.

---

3. 풀이 및 코드 분석

3.1. Recursion

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int testCase = Integer.parseInt(reader.readLine());
		
		for(int i=0; i<testCase; i++) {
			int k = Integer.parseInt(reader.readLine());
			int n = Integer.parseInt(reader.readLine());
			
			writer.write(findCitizen(k, n)+"\n");
		}
		
		writer.flush();
		reader.close();
		writer.flush();
	}
	
	private static int findCitizen(int k, int n) {
		if(k==0)
			return n;
		else {
			int sum = 0;
			for(int i=0; i<=n; i++) 
				sum += findCitizen(k-1, i);		
			return sum;
		}
	}
}

3.2. 다른 풀이 - 2차원 배열 

- 참고 : https://st-lab.tistory.com/78

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

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int testNumber = Integer.parseInt(reader.readLine());
		int[][] citizen = new int[15][15];
		
		findCitizen(citizen);
		
		for(int i=0; i<testNumber; i++) {
			int k = Integer.parseInt(reader.readLine());
			int n = Integer.parseInt(reader.readLine());
			writer.write(citizen[k][n]+"\n");
		}
		
		writer.flush();
		reader.close();
		writer.close();
	}
	
	private static void findCitizen(int[][] citizen) {
		for(int i=1; i<=14; i++) {
			citizen[i][1] = 1;
			citizen[0][i] = i;
		}
		
		for(int j=1; j<=14; j++) {
			for(int k=2; k<=14; k++) {
				citizen[j][k] = citizen[j-1][k] + citizen[j][k-1];
			}
		}
	}
}

---

4. 메모

• 문제를 이해하고, 쉽고, 문제를 작게 만들어서 해결하는 능력도 중요하지만, 2차원 배열을 이용한 풀이처럼 수학적으로 규칙성을 찾아 해결하는 능력도 중요하다고 생각한다. 
• 연습을 통해 그런 능력을 배양하자.