문제 설명
주어진 문제는 다음과 같습니다. 아파트의 층수와 각 층의 거주자 수에 대하여 부녀회장이 되기 위한
알고리즘을 작성해야 합니다. 특정 층의 거주자 수를 계산하는 알고리즘을 구현하는 것이 목표입니다.
아파트는 0층부터 N층(0 ≤ N ≤ 14)까지 있으며, n층의 k호에는 k명이 살고 있습니다.
예를 들어, 3층의 3호에는 3명이 살고 있습니다.
각 층의 주민 수는 아래와 같이 계산됩니다.
– 1층 : 1호 1명, 2호 2명, 3호 3명…
– 2층 : 1호 1명, 2호 3명, 3호 6명…
– n층의 k호에는 n층의 k-1호의 주민 수와 n층의 k호의 주민 수의 합이 저장된다.
입력 형식
첫 번째 줄에는 테스트 케이스의 수 T(1 ≤ T ≤ 100)가 주어집니다. 이후 T개의 줄에 걸쳐 각 테스트케이스마다
정수 N(0 ≤ N ≤ 14)과 K(1 ≤ K ≤ 14)가 제공됩니다. 여기서 N은 층수, K는 호수를 의미합니다.
출력 형식
각 테스트 케이스마다 n층 k호의 거주자 수를 출력해야 합니다.
예제 입력
2
1 3
2 3
예제 출력
3
6
문제 해결 과정
이 문제를 해결하기 위해, 우리는 동적 프로그래밍(Dynamic Programming: DP) 기법을 사용할 것입니다.
n층의 k호의 주민 수를 구하기 위해 아래의 관계를 사용할 수 있습니다.
주민수(n, k) = 주민수(n-1, 1) + 주민수(n, k-1)
여기서, 주민수(0, k) = k 그리고 주민수(n, 0) = 0으로 초기화합니다. 아래는 주민 수를 테이블에 저장하는
과정의 기본 단계입니다.
1단계: 초기화
먼저, 거주자 수를 저장하기 위한 2차원 배열을 선언하고 초기값을 설정합니다.
int[,] dp = new int[15, 15]; // 15층, 15호를 위한 배열
for (int i = 0; i <= 14; i++) {
dp[0, i] = i; // 0층의 k호에는 k명이 살고 있습니다.
}
2단계: DP 테이블 채우기
이중 반복문을 사용하여 dp 테이블을 채워나갑니다. n층과 k호의 경우를 모두 고려하여
아래와 같이 구합니다.
for (int n = 1; n <= 14; n++) {
for (int k = 1; k <= 14; k++) {
dp[n, k] = dp[n - 1, k] + dp[n, k - 1];
}
}
3단계: 결과 출력
모든 테스트 케이스에 대해 주민 수를 구하고 출력합니다. 아래는 최종 구현 예제입니다.
using System;
class Program {
static void Main(string[] args) {
int[,] dp = new int[15, 15];
for (int i = 0; i <= 14; i++) {
dp[0, i] = i;
}
for (int n = 1; n <= 14; n++) {
for (int k = 1; k <= 14; k++) {
dp[n, k] = dp[n - 1, k] + dp[n, k - 1];
}
}
int T = int.Parse(Console.ReadLine());
for (int t = 0; t < T; t++) {
string[] input = Console.ReadLine().Split();
int n = int.Parse(input[0]);
int k = int.Parse(input[1]);
Console.WriteLine(dp[n, k]);
}
}
}
결론
이번 문제를 통해 동적 프로그래밍의 기초 개념을 이해하고, 문제 해결 능력을 향상시킬 수 있었습니다.
이 문제는 알고리즘 테스트에서 자주 출제되는 유형 중 하나로, 다양한 변형이 존재합니다.
실제 코딩테스트에 응용하기 위해서는 DP 기법을 반복적으로 연습하는 것이 중요합니다.