[Java] 백준알고리즘 #2775 부녀회장이 될테야

백준알고리즘 #2775 부녀회장이 될테야 문제

위와 같은 조건을 가진 아파트에 a층 b호에 사는 사람의 수는 몇명인지 구하는 문제이다.

a층의 b호에는 a-1층의 1호부터 b호까지 거주하는 사람들의 수의 합 만큼의 사람이 살고 있다.

이를 숫자로 나열해보면

0층 : 1 2 3 4 5 ...

1층 : 1 3 6 10 15 ...

2층 : 1 4 10 20 35 ...
3층 : 1 5 15 35 70 ...
4층 : 1 6 21 56 126 ...

...

 

이 될 것이다.

 

먼저 k와 n을 입력받고 이 범위만큼의 2차원 배열을 생성한다.

int k, n;
k = sc.nextInt();
n = sc.nextInt();
int[][] a = new int[k + 1][n + 1];

 

배열은 0부터 시작하고, 이 아파트에는 0층이 있으므로 k+1, n+1 만큼의 범위를 지정했다.

0층에는 1 2 3 4 5 ... 만큼의 사람들이 살고 있으므로 0층에 사는 사람 수를 대입해준다.

for (int i = 1; i <= n; i++) {
	a[0][i] = i;
}

 

이제 각 k층의 n호에 사는 사람들을 구할 차례이다.

for (int i = 1; i <= k; i++) {
	int sum = 0;
	for (int j = 1; j <= n; j++) {
		sum += a[i - 1][j];
		a[i][j] = sum;

	}
}

a[k][n]에 사는 사람은 a[k-1][1] 부터 a[k-1][n]까지 사는 사람들의 수를 합한 만큼 살고 있다.

a[k-1][1]

a[k-1][1] + a[k-1][2]

a[k-1][1] + a[k-1][2] + a[k-1][3]

a[k-1][1] + a[k-1][2] + a[k-1][3] + a[k-1][4]

....

위와 같이 각 케이스를 저장하기 위한 sum변수를 만들어 0으로 초기화한다.

 

이 sum 변수에는 j가 1일때는 a[i-1][1] 값만 담겨서 a[i][1]에 저장될 것이고

차례로 j가 증가함에 따라 sum 변수 값이 증가하면서 a[i][j]에 각각 다른 값이 저장된다.

 

 

전체 코드를 보면 다음과 같다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int k, n, t;
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		int[] b = new int[t];
		for (int x = 0; x < b.length; x++) {
			k = sc.nextInt();
			n = sc.nextInt();
			int[][] a = new int[k + 1][n + 1];

			for (int i = 1; i <= n; i++) {
				a[0][i] = i;
			}
			for (int i = 1; i <= k; i++) {
				int sum = 0;
				for (int j = 1; j <= n; j++) {
					sum += a[i - 1][j];
					a[i][j] = sum;

				}
			}
			System.out.println(a[k][n]);
		}

	}

}