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

728x90

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

---

접근

• DP

---

풀이

문제의 설명을 보니 DP입니다라고 말을 하는 거 같았다. 아직 백준에서 어려운 문제를 손댈려면 한참 남은 거 같아서 중간중간 쉬운 문제들도 가져왔다. 문제는 아파트에 거주할려면 밑에 층의 1호부터  자기 호수까지 거주하는 사람 인원 총합계만큼 입주하여야 한다. 그 말은 밑에 층 부터 차근차근 인원수를 더하여 bottom-up 방식으로 채워나가면 될 것이다. 아파트 크기의 배열을 선언해 아파트를 인원수대로 다 채우고 나서 입력받는 호수의 값을 출력하기로 했다.

int[][] apart = new int[15][15];

for(int i = 1; i < 15; i++){
  apart[0][i] = i;
}

0층부터 14층까지로 크기가 15인 2차원 배열을 선언해 주고 0층의 인원을 초기화해줬다. 문제에서 0호는 존재하지 않음으로 1호부터 초기화한다. 아파트의 층과 호수가 15로 크지 않기 때문에 재귀를 사용해 입력받는 호수를 계산해 주는 것이 메모리 상으로 효율적인 방법일 수도 있지만 다른 범위가 큰 문제에서 재귀함수는 오버플로우가 날 수 있기 때문에 DP를 사용해 주어야 한다. 그리고 나는 재귀함수를 좋아하지 않기 때문에 바로 DP로 결정했다.

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

핵심 코드이자 이 문제의 전부다. DP 없이 1차원 적으로 문제를 푼다면 매 호수마다 반복문을 돌려 밑에 층 인원을 더해주어 계산해야 한다. 하지만 같은 층의 전 호수의 인원이 곧 아래층 전 호수의 인원을 더한 것과 같기 때문에 같은 층 전 호수의 인원과 아래층 동일 호수의 인원을 더해주면 된다. 예를 들어 3층의 8호에 입주할 것이라면 2층의 1호부터 8호까지의 인원을 모두 더한 만큼 사람을 데려와야 한다. 그런데 3층의 7호에 인원이 2층의 1호부터 7호까지의 인원을 더한 것과 같기 때문에 (3층 7호 == 2층 (1,2,3... 7)호) 3층 7호의 인원에 2층 8호 인원만 더해준다면 3층 8호의 값이 나온다. 그렇게 모든 층의 인원을 계산한 후 문제로부터 입력받는 층과 호수에 대응하는 값을 꺼내준다.

---

전체 코드

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        
        int[][] apart = new int[15][15];
        
        for(int i = 1; i < 15; i++){
            apart[0][i] = i;
        }
        
        for(int i = 1; i < 15; i++){
            for(int j = 1; j < 15; j++){
                apart[i][j] = apart[i-1][j] + apart[i][j-1];
            }
        }
               
        for(int i = 0; i < t; i++){
            int k = sc.nextInt();
            int n = sc.nextInt();
            
            System.out.println(apart[k][n]);
        }
    }
}

늘 느끼는 거지만 백준은 특히나 문제가 너무 모호하고 해석이 불분명해 대충 어떤 알고리즘 쓰라는 문제구나 하고 때려 맞추는 느낌이다. 문제 자체는 DP 알고리즘이 어떤 것이다를 연습해 볼 수 있는 괜찮은 문제인 것 같다.