[백준/Java]Q2775

백준 알고리즘 8단계 기본 수학1 2775번 문제입니다.

---

Q. 아래 조건과 같은 아파트가 있을 때, k층 n호에는 몇 명이 살고 있는지 출력하는 프로그램을 작성하시오.

[입력]
- 첫 번째 줄에 테스트 케이스 T가 주어진다.
- 각각의 케이스마다 첫 번째 줄에 정수 K, 두 번째 줄에 정수 N이 주어진다.

 

[조건]
- 1 ≤ K, N ≤ 14
- K층 N호에 살려면 자신의 아래(K-1)층의 1호부터 N호까지 사람들의 수의 합만큼 사람들이 살아야한다.
- 아파트는 0층부터 있고 각층은 1호부터 있으며 0층의 i호에는 i명이 산다.

풀이

문제를 풀기 위해 조건에 따라 아파트를 그려봤다.

아파트는 0층부터 있으며, 0층은 숫자가 1부터 +1씩 증가한다.

조건에 따라 K층 N호에 거주하는 사람 수는 K-1층의 0에서 N까지의 합이다.(x축의 초기값을 0으로 잡았기 때문에)

규칙이 어렵지 않아 2차원 배열과 반복문을 이용해 문제를 풀 수 있었다.

• [1][2] = [0][0] + [0][1] + [0][2]
• [2][3] = [1][0] + [1][1] + [1][2] + [1][3]
• [3][4] = [2][0] + [2][1] + [2][2] + [2][3] + [2][4]

 

소스

package com.baek.algo;

import java.util.Scanner;

public class Q2775 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int t = sc.nextInt();

		for(int i = 0; i < t; i++) {
			int k = sc.nextInt();
			int n = sc.nextInt();

			if(n >= 14) n = 14;

			int[][] arr = new int[k + 1][n];

			for(int x = 0; x <= k; x++) {
				for(int y = 0; y < n; y++) {
					int sum = 0;

					if(x == 0) {
						arr[x][y] = y + 1;
					} else {
						for(int j = 0; j <= y; j++) {
							sum = sum + arr[x-1][j];
						}
						arr[x][y] = sum;
					}
				}
			}

			System.out.println(arr[k][n-1]);
		}

		sc.close();
	}
}