[백준] 브1 > 부녀회장이 될테야 2775번 - JAVA

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

 

문제는 제목과 동일

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

a : 3
b : 2

2층의 1호부터 2호까지 사람들을 데려와 살아야 함

TestCase의 수 맨처음 주어짐 2
k : 1
n : 3

k : 2
n : 3

0층부터 있음
0층의 i호에는 i명이 산다.

---

Think🤔

 

0층부터 있음
0층의 i호에는 i명이 산다.

[ 1번 케이스 ] 
1층 3호에 살고 싶으면
0층의 1호에는 1명 , 2호에 2명 , 3호에 3명 
그럼 6명을 데려와야 함.

[ 2번 케이스 ]
2층의 3호에 살고 싶으면
0층에 1,2,3 6명
1층에 1,2,3 6명
2층 1,2

그럼
0층 1호 : 1명
0층 2호 : 2명
0층 3호 : 3명

1층 1호 : 1명
1층 2호 : 0층 1호 + 0층 2호 = 1 + 2 = 3명
1층 3호 : 1+2+3 = 6명

2층 1호 : 1명 
2층 2호 : 4명 
2층 3호 : 1+3+6 = 10명

3층 1호 : 1명
3층 2호 : 5명
3층 3호 : 1+4+10 = 15명
★
0층
1 2 3 4
1층
1 3 6 10
2층
1 4 10 20
3층
1 5 15 35

n층 k호 : (n-1) 1 ~ (n-1) k
재귀 이용해서 푼다음 줄이기

public static Integer chk(int n , int k){

if(n == 0){return k;} // 각각 층이면 각 호수만큼 사람이 산다.

int re = 0;
for(int i=1; i<=k; i++){ // 전층의 k호수만큼 돌려야함
re += chk(n-1,i)
}
return re;
}

---

Solution✍

 

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

class Main{
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Integer li = Integer.parseInt(br.readLine());
		
		for(int i=0; i<li; i++){
            Integer n = Integer.parseInt(br.readLine());
		    Integer k = Integer.parseInt(br.readLine());
			System.out.println(chk(n,k));
		}
	}
	
	public static Integer chk(int n , int k){

		if(n == 0){return k;}  // 0층일 경우 해당 호수만큼 사람 출력
		
		int re = 0;
		for(int i=1; i<=k; i++){ // 1명씩 있으므로 i는 1부터
			re += chk(n-1,i);
		}
		return re;
	}
}

---

Review🤩

 

재귀함수를 잘 사용해야함.

---