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

1. 0층에 사는 사람 수를 배열에 저장함

2. 1의 배열을 이용해서 1층의 n호실까지 그 방에 살기 위해 데려와야 하는 사람의 수를 구해서 배열에 새로 저장함

3. 업데이트된 배열을 이용해 k-1층까지 반복.

이런 방식으로 문제를 해결했다.

 

부족한 설명이지만, 문제에 주어진 예제 입력인 k = 1, n = 3으로 예를 들어보겠다.

 

맨 처음 0층에 사는 사람 수를 저장하고 있는 배열은 이렇다.

{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0} (문제에서 1호부터 시작한다고 했으니 인덱스 0번을 1호로 삼았다.)

 

이것을 이용해 1층의 3호실까지 살기 위해서 필요한 사람 수를 구해서 다시 배열에 저장한다.

 

{ 1, 1+2, 1+2+3, .....} n호실 이후는 필요하지 않으니 무시한다.

{1, 3, 6, ....} 이것이 1층의 1호, 2호, 3호에 살기 위해 데려와야 할 사람수를 저장한 배열이다.

1층 3호에 살고 싶다면 이 배열에서 세 번째값인 6명을 데려오면 된다.

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

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트케이스의 개수를 입력받음
        StringBuilder sb = new StringBuilder(); // 출력할 때 사용하기 위한 것
        
        for(int i=0;i<T;i++){ // 테스트케이스 수 만큼 반복
            int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,0}; // 0층에 사는 사람 수
            // 1호부터 시작하는데 호수 n은 14까지 가능하기 때문에 15개짜리 배열로 만듦
            int k = Integer.parseInt(br.readLine()); // 층수를 입력받음
            int n = Integer.parseInt(br.readLine()); // 호수를 입력받음
            int sum = 0; // k-1층의 1호부터 n호까지 사는 사람을 세기 위한 변수
            
            for(int j=0;j<k;j++){ 
                for(int l=0;l<n;l++){
                    arr[l] = sum+arr[l]; // 한 층의 n호까지 사는 사람 수를 더해서 배열에 새로 저장함
                    sum = arr[l];
                    }
                sum = 0; // 다음 층에 사는 사람 수도 계산하기 위해서 0으로 초기화
            	}
                
            sb.append(arr[n-1]).append('\n'); // 마지막에 한번에 출력하기 위해 스트링빌더에 값 추가
            }
        System.out.print(sb); // 필요한 사람 수를 출력함
        }
    }

문제를 해결하긴 했으나 무려 삼중반복문이라 효율적인 풀이는 아닌 것 같다.

개선시킬 수 있는 방법을 더 고민해봐야겠다...