[Dev-Ping9] 백준 2775번 - 부녀회장이 될테야 (Java)

... 다 작성하고 저장을 안했다.... 😥

 

 

# 문제 설명

• k>=1, n<=14 인줄 알고 dp로는 절대 풀면 안되겠구나 라는 생각을 하곤, k와 n으로만 이루어진 수학적인 식이 있을까 한참 고민했었다... 🙄 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 이걸 3시간 잡고있던 내가 레전드...
• 결론은 k와 n의 크기가 크지 않고, 전 단계의 부분계산의 결과가 다음단계의 계산결과에 쓰인다는 것이 문제 자체에 정의되어있기 때문에 쉽게 DP로 접근하면 되겠구나라고 생각 할 수 있다.
• 손으로 몇번만 규칙을 따라가면, 매우 다양한 점화식을 찾을 수 있다. 

 

# 사용할 점화식

• dp[i][j] : i층 j호의 거주인원
• dp[i][j] = dp[i-1][j] + dp[i][j-1]

 

 

# 구현 코드

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

public class Main{
    static int[][] arr= new int[15][15];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int times = Integer.parseInt(br.readLine());
        int k,n;

        for(int i=0;i<15;i++){
            arr[i][1] = 1;
            arr[0][i] = i;
        }
        for(int i=1;i<15;i++){
            for(int j=2;j<15;j++){
                arr[i][j] = arr[i][j-1]+arr[i-1][j];
            }
        }

        for(int i=0; i<times; i++){
            k = Integer.parseInt(br.readLine()); 
            n = Integer.parseInt(br.readLine()); 
            System.out.println(arr[k][n]);
        }
    }
}