백준 알고리즘 2775번 문제풀이(JAVA)

이 문제는 별로 어렵지 않게 풀었다.

 

주의해야 할 점은 0층부터 14층까지 있다는 것. -> 인덱스 주의해야한다.

다음과 같은 방식과 푼 건 최대 입력값이 14로 굉장히 작기 때문에 저렇게 다 구해놓고 바로 찾는게 가능하다.

 

---

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[][] arr = new int[15][15];
        int sum = 0;

        for(int i=0;i<arr.length;i++) {
            for(int j=1;j<=arr.length - 1;j++) {
                if(i==0) {
                    arr[i][j] = j;
                }else {
                    sum += arr[i-1][j];
                    arr[i][j] = sum;
                }
            }
            sum = 0;
        }

        int T = Integer.parseInt(br.readLine());
        for(int i=0;i<T;i++) {
            int k = Integer.parseInt(br.readLine());
            int n = Integer.parseInt(br.readLine());

            System.out.println(arr[k][n]);
        }
    }

}

---

 

문제를 풀고 나서 다른 분이 푼 풀이도 찾아봤는데 훨씬 더 간단한 로직이 있었다. 내가 푼 방식은 일일이 계속 sum을 구하기 때문에 똑같은 행위를 반복하는 것이다. 이건 중복에 해당되므로 깨끗한 코드?라고 볼 순 없을 것 같다.

 

for(int i=1;i<arr.length;i++) {
    arr[0][i] = i;
    arr[i][1] = 1;
}

for(int i=1;i<arr.length;i++) {
   for(int j=2;j<arr.length;j++) {
       arr[i][j] = arr[i][j-1] + arr[i-1][j];
   }
}

 

이전 인덱스의 값들을 이용해 쉽게 구할 수 있다. 그림으로 생각해보면 [자기 왼쪽 호의 값 + 자기 바로 아래 층의 값]이라고 생각하면 된다.