[재귀] 백준 2775번 부녀회장이 될테야 - JAVA

 

 

오늘도 풀어보는 과거 내가 못풀었던 문제!

나는 이 문제를 재귀로 풀어보았다.

 

---

1. 출처

---

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

2775번: 부녀회장이 될테야

 

 

 

무려 파이썬으로 2년전 실패했던 문제다 ㅎㅎ..

싸피에 들어와 재귀를 배우고 문제를 풀어보니 감회가 색다르다.

 

 

 

---

2. 설계

---

 

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

[각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.]

[1 ≤ k, n ≤ 14]

 

이 문구가 이 문제의 정체성이라고 해도 과언이 아니다.

k는 층이고, n은 호인데, 호에 대한 제한만 있어서 미리 계산을 해둔 테이블을 만들 순 없을 것 같다.

 

1
1
1
1
1	...
1	3	6	10	15	21	28
1	2	3	4	5	6	7	...

 

다음 테이블은 0층 1호부터 시작하는 아파트 인원수이다.

이런식으로 같은 색깔끼리 더해 다음 수가 나오는 것을 알 수 있다.

 

예를 들어 1층 2호에 살고 싶다고 한다면,

0층 2호 + 1층 1호 = 2층 2호

2 + 1 = 3

 

이라는 결과가 도출된다는 것을 확인할 수 있다.

 

여기서 도출되는 식은

아파트 k층 n호 = 아파트 k-1층 n호 + 아파트 k층 n-1호 이다.

 

 

---

3. 전체 코드

---

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		
		int t = sc.nextInt();
		
		
		for(int T=1;T<=t;T++) {
			int floor = sc.nextInt();//층 == k
			int N = sc.nextInt();//호 == n
			
			int result = setAPT(floor, N);
			
			System.out.println(result);
		}
	}
	
	public static int setAPT(int floor, int N) {
		
		//호수가 0이면 0
		if(N == 0) return 0;
		else if(floor==0) return N;
		else return setAPT(floor, N-1) + setAPT(floor-1, N);
		
	}

}

 

 

---

오늘도 끝!