반응형
오늘도 풀어보는 과거 내가 못풀었던 문제!
나는 이 문제를 재귀로 풀어보았다.
1. 출처
https://www.acmicpc.net/problem/2775
2775번: 부녀회장이 될테야
첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다
www.acmicpc.net
무려 파이썬으로 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);
}
}
오늘도 끝!
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[문자열] 백준 1593번 문자 해독 - JAVA (0) | 2023.06.25 |
---|---|
[BFS/DFS/MST] 백준 17472번 다리 만들기2 - JAVA (0) | 2023.06.23 |
[구현] 백준 2564번 경비원 - JAVA (0) | 2023.06.20 |
[그리디] 백준 26099번 설탕 배달2 - JAVA (3) | 2023.06.20 |
[누적합] 백준 11659번 구간 합 구하기 4 - JAVA (2) | 2023.06.02 |