[JAVA 자바] 백준 2775번 : 부녀회장이 될테야

▶ 문제

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

2775번: 부녀회장이 될테야

▶ 설명

k층 n호 방에 기거하게 될 구성원 수를 구해야 한다.

0층엔 n호만큼의 인원이 살고 있고

1층부터 올라갈 수록 아래층의 인원에서 누적 합을 구하여야 한다.

 

 

 

결국 옆 집과 (이전 호 수) 아래층의 동일 호의 인원을 구하면 된다.

 

점진적으로 누적해서 합을 구한 값을 이용해야 하므로 배열을 만들어서 했다.

층을 행, 몇호인지는 열로 보고 2차원 배열을 만들었다.

주의해야 할 점은 층은 0부터 시작하는 반면 호는 1부터 시작한다.

(0호는 구색만 갖춘 것이다.)

0층은 고정된 수가 값으로 들어가므로 결국 1부터 시작한다고 볼 수 있다.

다행히도 문제에서 14층, 14호 까지 되어있는 건물이라고 범위를 정해 주었다. 그러므로 배열의 크기는 행과 열이 각각 15, 15개가 된다. 총 배열의 크기는 30개인 것이다.

 

그리고 입력으로 들어오는 k와 n을 배열의 k행과 n 열까지 반복문을 통해 값을 구한다. 

즉 배열 전체에 값을 모두 부여할 필요가 없는 것이다. 입력된 값 만큼만 배열 값을 구하면 된다.

 

테스트 케이스마다 건물의 범위가 다르다면 (층과  호 수의 개수가 테스트케이스마다 다르다면) 

각각 다른 배열을 선언하고 값을 주도록 해야 하지만 

이 문제에서는 건물의 범위가 일정하기 때문에 배열을 한번만 선언한 후 값이 들어가지 않았을 때에만 넣어주도록 하면 연산의 반복을 줄일 수 있다.

그래서 배열에 값이 들어가지 않았을 때를 체크하여 값이 없을 때에만 연산을 하도록 하는 코드를 넣었다.

 

 

▶ 문제 풀이

🌱 풀이.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt(br.readLine());

		int arr[][] = new int[15][15];
		while (t-- > 0) {
			int k = Integer.parseInt(br.readLine());
			int n = Integer.parseInt(br.readLine());

			for (int i = 0; i <= k; i++) {
				for (int j = 1; j <= n; j++) {
					if (arr[i][j] == 0) {
						if (i == 0) {
							arr[i][j] = j;
						} else {
							arr[i][j] = arr[i][j - 1] + arr[i - 1][j];

						}
					}
				}
			}

			sb.append(arr[k][n]).append("\n");
		}

		System.out.println(sb);
	}

}

 

 

 

 

▶ Log