[백준 2775번] 부녀회장이 될테야 (java)

링크

나의 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = "";  // 입력받는 문자열
        int T, k = 1, n = 1;
        int maxK = 0, maxN = 0;
        ArrayList<int[]> input = new ArrayList<int[]>();
        int[][] apart;
        T = Integer.parseInt(bf.readLine());    // T 개의 테스트 실시
        for (int i = 0; i < T; i++) {
            k = Integer.parseInt(bf.readLine());    // k층
            n = Integer.parseInt(bf.readLine());    // n호

            if (k > maxK)
                maxK = k;   // 가장 큰 k층 찾기
            if (n > maxN)
                maxN = n;   // 가장 큰 n호 찾기

            int[] temp = new int[2];
            temp[0] = k;
            temp[1] = n;
            input.add(temp);    // 입력받은 내용은 input에 저장해둠 (나중에 다시 조회해서 쓸거)
        }
        // 가장 큰 k값과 가장 큰 n 값을 갖는 아파트를 건설해서
        // 값을 채운 후, input에 맞는 값만 반환할 예정
        apart = new int[maxK+1][];   // 0 ~ k 까지.
        // 층은 0층부터 존재하기 때문에, 0 ~ k층까지 index로 갖기 위해 maxK+1로 정의

        // 계산의 바탕이 되는 0층 입력 (0층 1호부터 0층 n호 까지..)
        int[] f = new int[maxN];   // 한 층에 대한 int[maxN]. index로 0 ~ maxN-1까지 갖는다.
        for (int number = 0; number < maxN; number++) {
            f[number] = number+1;
        }
        apart[0] = f;


        // 1층부터 maxK층까지 증축을 시작
        for (int floor = 1; floor <= maxK; floor++) {
            f = new int[maxN];  // 새로운 층 생성
            int sum = 0;

            // floor층 계산하기
            for (int number = 0; number < maxN; number++) {
                sum += apart[floor-1][number];  // floor-1층 number호의 사람을 구함 (index 조회기 때문에 number = 0부터..)
                f[number] = sum; // floor-1층의 1호 부터 number호 까지의 합을 대입함
            }

            apart[floor] = f;
        }

        // 전체 아파트 출력하는 함수
        //printApart(apart);

        for (int[] inp : input) {
            System.out.println(apart[inp[0]][inp[1] - 1]);  // 전체 아파트에서 원하는 k층 n호 값만 출력 (n호는 -1 해주는 것에 주의)
        }
    }

    public static void printApart(int[][] apt) {
        // 입력받은 아파트를 출력하는 함수
        // 맨 아래서부터 0층
        int apartSize = apt.length;
        for (int fl = apartSize - 1; fl >= 0; fl--) {
            for (int num : apt[fl]) {
                System.out.printf("%3d ", num);
            }
            System.out.println();
        }
    }
}

최초에는 재귀로 풀어야겠다고 판단하여 재귀로 돌렸다. 하지만 재귀로 돌렸을 시에는 0층부터 쌓아올리는 작업을 불필요하게 반복했기에 300 ms 가 나왔다. 이를 개선하기 위해, 가장 큰 k와 n을 찾아, 그만큼의 아파트를 미리 만들어둔 후 필요한 위치 값만 가져오기로 했다.

이 과정에서도 k층은 0 ~ k층까지 있지만, n호는 1부터 n호까지 였기 때문에 헷갈리지 않게 유의하면서 작업해야 했다.

속도도 120 ms로 다른 사람들과 비슷했기 때문에 뿌듯했다..

내가 생각한 다른 사람의 모범 답안

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        int chart[][] = new int[15][14];
        for(int i = 0;i<14;i++){
            chart[0][i] =i+1;
            chart[i][0] = 1;
        }
        chart[14][0]= 1;
        for(int x = 1; x<15;x++) {
            for(int y = 1;y<14;y++){
                chart[x][y] = chart[x][y-1] + chart[x-1][y];
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i =0; i<testCase;i++) {
            int floor = Integer.parseInt(br.readLine());
            int room = Integer.parseInt(br.readLine());
            sb.append(chart[floor][room-1]).append("\n");
        }
        System.out.println(sb);
    }
}

가장 빠른 속도를 기록한 코드이다. 아파트의 입력 범위가 정해져있기 때문에 이를 이용해서 아파트 전체를 미리 작성했다.
또한 나의 코드는 문제에서 주어진 대로 아래 층들을 더해가는 식이었지만, 이 코드는 "옆값 + 아랫값"으로 더 코드가 간결하고 쉽게 구현했다.

이 코드를 보고 더욱 더 가독성 좋은 코드를 만들기 위해 다짐한다..

실행 결과

• 나의 코드 : 120 ms
• 모범 답안 : 116 ms