[JAVA] 백준 2775_부녀회장이 될테야

 

[문제링크]

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

 

 

📌 문제 탐색하기

아파트의 특정한 층과 호에 사는 사람 수를 구하는 문제이다.

각 호수에 사는 사람의 수는 아래층 사람의 수를 기반으로 계산하기 때문에 중복 계산을 방지하기 위해

동적 프로그래밍 DP를 활용해서 구현하면 되는 문제라고 생각함.

📌 가능한 시간복잡도 

DP의 시간 복잡도는 주어진 테이블 크기에 따라서 결정되기 때문에 문제 조건에 주어진 층수 k와 호수 n으로 결정된다.

모든 층과 호에 있는 사람의 수를 구하기 위해서는 우리가 구하고 싶은 k층 한칸 아래의 1호부터 n호 까지의 합으로 계산되기 때문에

가능한 시간 복잡도는 O(K*N)이라고 생각합니다.

 

📌 코드 설계하기

우선 dp를 사용한 문제이기 때문,,,

 

• dp[0][n]=n: 0층의 n호 =>  n명 거주
• dp[k][1]=1dp[k][1] = 1dp[k][1]=1   =>  각 층의 1호에는 항상 1명 거주 

이런식으로 배열을 초기화 처리해서 문제 풀어주면 된다. 

 

 

 

📌 정답 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        int[][] dp = new int[15][15];

        for (int i = 0; i <= 14; i++) {
            dp[0][i] = i; // 0층 i호에는 i명
            dp[i][1] = 1; // i층 1호에는 1명
        }

     
        for (int k = 1; k <= 14; k++) { // 층
            for (int n = 2; n <= 14; n++) { // 호
                dp[k][n] = dp[k][n - 1] + dp[k - 1][n];
            }
        }

        for (int t = 0; t < T; t++) {
            int k = sc.nextInt(); // 층
            int n = sc.nextInt(); // 호
            System.out.println(dp[k][n]);
        }

        sc.close();
    }
}