2775 : 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

 

누가 이거 제목 보고 웃으라고 했습니까

대답합니다

 

자 오늘은 부녀회장이 될 시간이다.

아파트 짱 먹는거지

 

원리 자체는 Dynamic Programming이다

한칸씩 한칸씩 계산해서 최종적으로 우리가 원하는 호수의 인원을 세는 것으로

Memoization 기법을 이용하면 쉽게 풀 수 있다.

 

201호이면 101호

202호이면 101호 + 102호 

203호이면 101호 + 102호 + 103호 이런 식이다

 

자, 그렇다면 203호를 구하고자 할때 202호 + 203호이면 편하게 구할 수 있지 않을까?

203호 = (101호 + 102호) + 103호 = 202호+ 103호이니 말이다.

 

이 문제에서 현실성은 잠시 접어두고 복도식 아파트를 생각하면 편하다.

1호부터 자신의 아랫집에 있는 세대원들을 모두 합하는 문제이므로

(호수 기준)

1+2+3+4+...+b호까지의 합을 구하면 된다.

다만 이거를 일반적인 방법으로 구하고자 한다면 시간초과가 날 것이다.

 

 

Dynamic Programming에 대해서는 별도로 서술하도록 하겠다.

 

 

import java.util.*;
import java.io.*;

public class Main {
	static int[][] Apartment;

	static int Calculate(int floor, int HouseNumber) {
		int answer=0;
		for(int i=0;i<floor;i++)
		{
			for(int j=0;j<HouseNumber;j++)
			{
				Apartment[i+1][j+1]=Apartment[i+1][j]+Apartment[i][j+1];
			}
		}
		return Apartment[floor][HouseNumber];
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		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();

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

			for (int j = 0; j <= n; j++) {
				Apartment[0][j] = j;
			}
			for (int j = 0; j <= k; j++) {
				Apartment[j][0] = Apartment[0][0];
			}
			System.out.println(Calculate(k, n));
		}

	}

}