2775번 문제 : 부녀회장이 될테야

2775번: 부녀회장이 될테야 (acmicpc.net)

2775번: 부녀회장이 될테야

간단해보였는데 알고리즘을 생각하는게 생각보다 복잡했다 ,,.,

어떻게 했냐면 일단 0층의 i층에는 i명이 사니까 0층 인원을 반복문을 돌려서 저장했다.

그다음엔 1층 1호부터 인원을 채웠는데

for(int i=1;i<arr.length;i++){

  int number = 0;

  for(int j=1;j<arr.length;j++{

    arr[i][j] = arr[i-1][j] + number;

    number = arr[i][j];

  }

}

반복문을 이렇게 작성했다. 

의미는 

arr[i][j] = arr[i-1][j] + number;

    3층 3호 인원 =  3층 2호 + 2층 3호 이기 때문에 3층 2호는 j반복문을 돌면서 구해지는 바로 직전의 값이기 때문에 그거를 number = arr[i][j];로 number에 넣어놓고 2층 3호를 배열에서 구한다. 끗 ..!

이렇게 해도 되고 아니면

3층 3호 인원 arr[i][j]= arr[i-1][j] + arr[i][j-1]; 이거를 반복문으로 구해도 된다 

package algorithm;

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));
				
		int num = Integer.parseInt(br.readLine());
		int apart[][] = new int[15][15];
		
		//0층 인원 저장
		for(int i=1;i<apart.length;i++) {
			apart[0][i] = i;
		}
		//1층 1호부터 인원 저장
		for(int i=1;i<15;i++) {
			int number = 0;
			for(int j=1;j<apart[i].length;j++) {
				if(j==1) apart[i][j] = 1;
				else 
				apart[i][j] = apart[i-1][j]+number;
				number = apart[i][j];
			}
		}
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<num;i++) {
			int k=Integer.parseInt(br.readLine());
			int n = Integer.parseInt(br.readLine());
			sb.append(apart[k][n]+"\n");
		}
		System.out.println(sb);
	}
}