이번 글에서는 자바 코딩테스트의 유명한 문제 중 하나인 “부녀회장이 될 테야” 문제를 살펴보겠습니다.
이 문제는 동적 프로그래밍의 기초를 배울 수 있는 좋은 사례로, 효율적인 알고리즘을 통해 주어진 문제를 해결하는 과정을 자세히 설명하겠습니다.
문제 설명
부녀회장이 될 테야는 다음과 같은 문제입니다.
문제:
아파트가 N층 K개가 있다고 가정할 때, K층 N호에 살고 있는 사람의 수를 구하는 알고리즘을 작성하세요.
아파트의 각 호수에는 K층 N호에 사는 사람 수를 구하는 문제가 있습니다. 0층은 모두 1명이고, 각 층의 N호에 있는 사람 수는 아래층의 모든 호수의 사람 수의 합입니다. 그러므로,
- 0층 1호 = 1
- 0층 2호 = 1
- 1층 1호 = 1
- 1층 2호 = 1 + 1 = 2
- 2층 1호 = 1
- 2층 2호 = 1 + 2 = 3
와 같은 패턴이 나타납니다.
주어진 K층과 N호에 대해, 해당 호수에 살고 있는 사람의 수를 구하는 함수를 만들어주세요.
입력 및 출력 형식
입력: 첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 14)가 주어집니다.
각 테스트 케이스는 두 개의 정수 K, N (0 ≤ K ≤ 14, 1 ≤ N ≤ 14)로 구성되어 있습니다.
출력: 각 테스트 케이스마다 K층 N호에 사는 사람 수를 출력하세요.
문제 풀이 과정
1단계: 문제 이해하기
문제의 본질은 0층에서 K층까지의 사람 수 패턴을 이해하고, 이 패턴을 기반으로 N호에 사는 사람 수를 구하는 것입니다.
이해한 바에 따르면, 아파트 문제는 동적 프로그래밍의 규칙을 적용할 수 있습니다.
즉, 각각의 층에서 N호의 값은 이전 층에서의 N호와 (N-1)호의 합으로 정의될 수 있습니다.
2단계: 동적 프로그래밍 테이블 설계
이 문제를 해결하기 위해, 우리는 K층 N호를 계산하기 위한 2차원 배열을 선언합니다.
이 배열을 통해 각 위치에 사람 수를 채워넣는 방식으로 진행합니다.
// 자바 코드 예시
int[][] dp = new int[15][15]; // 15 x 15 배열 선언
for (int i = 0; i < 15; i++) {
dp[i][1] = 1; // 0층의 모든 호수에 대해서 초기화
dp[0][i] = i; // 0층의 사람 수 설정
}
for (int i = 1; i < 15; i++) {
for (int j = 2; j < 15; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 동적 프로그래밍 점화식
}
}
3단계: 최종 계산
위의 규칙을 기반으로 K층 N호에 대한 값을 계산할 수 있습니다. 각 테스트 케이스마다 dp[K][N]의 값을 출력하면 됩니다.
4단계: 코드 구현
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 테스트 케이스 수
int[][] dp = new int[15][15]; // 15x15 배열
// DP 배열 초기화
for (int i = 0; i < 15; i++) {
dp[i][1] = 1; // 0층의 모든 호수 초기화
dp[0][i] = i; // 0층의 사람 수 설정
}
// DP 테이블을 채우기
for (int i = 1; i < 15; i++) {
for (int j = 2; j < 15; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 점화식
}
}
// 각 테스트 케이스 처리
for (int t = 0; t < T; t++) {
int K = sc.nextInt(); // 층 수
int N = sc.nextInt(); // 호 수
System.out.println(dp[K][N]); // 결과 출력
}
sc.close();
}
}
결론
이번 강좌를 통해 “부녀회장이 될 테야” 문제를 해결하는 과정과 관련된 동적 프로그래밍의 기초를 이해하셨기를 바랍니다.
이 문제는 알고리즘 설계 및 구현의 중요한 원리를 배울 수 있는 좋은 사례입니다.
다양한 문제에 이와 같은 패턴을 적용하면 더 복잡한 문제도 상대적으로 쉽게 풀 수 있습니다.
연습을 통해 더 많은 유형의 문제를 해결해 보시기 바랍니다!