[BOJ - JAVA] 2775 - 부녀회장이 될테야(수학, DP)

# 주소

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

2775번: 부녀회장이 될테야

# 문제

# 문제 해설 및 코드 리뷰

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] arr = new int[n];
		int count = 0;
		while(count != n) {
			int x = scan.nextInt();
			int y = scan.nextInt();
			int [][] dp = new int[x+1][y];
			// 1 4 10
			// 1 3 6
			// 1 2 3
			for(int i = x; i >= 0; i--) {
				for(int j = 0; j < y; j++) {
					if(i == x) {
						dp[i][j] = j+1;
					}else if(j == 0){
						dp[i][j] = 1;
					}else{
						for(int k = 0; k < j+1; k++) {
							dp[i][j] += dp[i+1][k];
						}
					}
				}
			}
			arr[count] = dp[0][y-1];
			count++;
		}
		for(int i = 0; i < n; i++) {
			System.out.println(arr[i]);
		}
	}
}

while문 안에 3중 for문이 들어가야 하나 싶지만 입력값이 크지 않기에 시간초과는 나지 않았습니다.

차례대로 설명을 해보자면 제일 처음 입력값이 테스트 케이스이므로 n을 입력 받습니다. 

그리고 while문으로 들어가서 x와 y를 while문이 실행될 때마다 입력을 받습니다. 그리고 입력받은 x,y는 방의 층과 호수를 뜻하는데, 이 아파트의 방은 기본적으로 아래층의 이전 호수의 모든 방의 인원을 합한 인원이 위층에 살고 있습니다.

그러므로 0층에는 1,2,3명이 산다고 가정했을 때 1층의 인원에는 1,3,6명이 살게 되는 것입니다. 그러면 자연스럽게 2층의 인원은 1, 4, 10명이 살게 된다고 생각할 수 있겠습니다.

그러므로 int i == x일 때는(0층을 뜻합니다) 1,2,3명씩 순서대로 입력해주고 만약 j값이 0일때는 1호실의 인원이므로 모두 1명을 삽입합니다. 그리고 그 외의 호실에서는 아래층의 이전호실부터 해당 아래 호층까지 인원을 합해주면 되는데요. 이 때는 다시 for문으로 들어가서 해당 입력된 값을 모두 더하여 저장합니다.

최종적으로 arr에 더해진 dp값을 넣고 모든 테스트케이스에 한해 실행이 되고 나면 arr를 출력해주시면 원하는 정답을 출력할 수 있겠습니다. 

감사합니다.