class2 - 2775번 부녀회장이 될테야 (자바)

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

 

제한 시간이 0.5초로 아주 짧다.

이 문제를 봤을 때 처음 떠올렸던 방식이 아예 처음에 2차원 배열을 초기화 시키는 방식이었다.

그러나 최대 층수도 안정해져있고, for문을 돌리기에는 제한 시간이 너무 적어서 다른 방법을 고안해냈다.

그러다 떠올린 방법이 재귀함수를 이용하는 방법이었다.

어차피 k층 n호 사람 수 = k-1층 1~n호 사람 수의 합 이니까 재귀 함수를 통해서 구현할 수 있다고 생각했다.

 

문제 풀기전 계획

k층 sum(n호 사람 수) = k-1층 sum(1호 ~ n호 사람 수) 

arr[15] = { 1....14}


a(int k층, int n호){
	if (k == 0)
	{
		return arr[n];
	}
	else {
		int temp = 0;
		for (int i = 0; i < n호; i++) {
			temp += a(int k - 1층, int i호);
		}
		return temp;
	}
		
}

문제 풀기 전 이런식으로 큰 틀을 짠 다음에 실제 코드를 짰다.

 

풀이

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

public class Main
{
    static int[] zeroFloorPeopleNum = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
	public static void main(String[] args) {
		try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            
            int caseNum = Integer.parseInt(br.readLine());
            int[] results = new int[caseNum];
            
            for (int i = 0; i < caseNum; i++) {
                int floor = Integer.parseInt(br.readLine());
                int roomNum = Integer.parseInt(br.readLine());
                
                results[i] = countPeople(floor, roomNum);
            }
            
            for(int result : results) {
                bw.write(String.valueOf(result)+"\n");
            }
            
            
            br.close();
            bw.flush();
            bw.close();
		}
		catch (IOException e) {
          System.out.println("IOException 발생");
		}
		
	}
	
	
	public static int countPeople(int floor, int roomNum) {
	    if (floor == 0) {
	        return zeroFloorPeopleNum[roomNum];
	    }
	    else {
	       int sum = 0;
	       for (int i = 1; i <= roomNum; i++) {
	           sum += countPeople(floor - 1, i);
	       }
	       
	       return sum;
	    }
	}
	
}

정답을 맞추고 다른 사람들은 어떻게 짰나 궁금해서 찾아봤는데 다른 문제랑 다르게 사람마다 풀이가 다 다르고, 다양해서 신기했다.