[자바] 백준 15489 - 파스칼 삼각형 (java)

 문제 : boj15489

---

 

필요 알고리즘 개념

• 동적계획법(DP)
  
  • 사실 딱히 DP 개념은 필요없다. 풀고보니 파스칼 삼각형 데이터 마련하는게 DP 느낌인거지, 그냥 구현문제다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  최근에 어떤분의 질문으로 3차원 파스칼 삼각형에 대한 설명이 이해안된다고 해서 그려서 설명해줬었는데, 마침 백준에 파스칼 삼각형이 보이길래(이 문제는 2차원이긴 하다) 한번 풀어봤다. 아래 이미지는 설명해준다고 그렸던걸로 이 문제와는 관계없다. ㅋㅋㅋ TMI로 윈도우에 기본으로 깔려있는 3D그림판을 쓰면 저렇게 어설프게나마 3D로 그릴 수 있다.

 

 

  우선 문제에서 제시된 삼각형을 코드적으로 어떻게 표현할지 생각해보자. 좌측으로 쫙 붙여서 2차원 배열로 표현해보면 될 것이다. 아래 이미지는 파스칼 삼각형에서 4번째줄까지 배열로 표현해본 것이다.

 

  또한, 보다시피 하삼각행렬(Lower Triangular Matrix) 형태이므로 가변배열로 표현하면 좋을 것이다. 즉 아래처럼 표현하면 된다. 자바에선 int[][] arr = new int[n][]; 이후 arr[0] = new int[1]; arr[1] = new int[2]; ... 이런식으로 가변배열을 만들 수 있다.

 

  이제 자료구조(가변배열을 통한 하삼각행렬 형태)는 정했으니, 기본 데이터를 구해보자. 입력을 받은 후 구하려고 하면 생각할게 더 많아진다. 그리고 어차피 최대 30줄까지만 만들면 되므로(C+W<=30, R+W<=30, W<=29 임에 따라 30줄까지만 만들면 됨을 알 수 있다.), 미리 만들어두면 된다. 코드는 아래와 같다. 가변배열 틀을 만들어주고, arr[1][1] = 1을 기본값으로 해서 해당 값이 실제론 좌우로 내려가야하지만 내 경우엔 좌측으로 전부 밀었으므로 그 아래와 그 오른쪽 아래로 내려가면 된다.

private static final int LIMIT = 30;

private int[][] getPascalTriangle() {
    int[][] arr = new int[LIMIT+1][];
    for (int i = 1; i <= LIMIT; i++) {
        arr[i] = new int[i+1];
    }
    arr[1][1] = 1;
    for (int i = 1; i < LIMIT; i++) {
        for (int j = 1; j <= i; j++) {
            arr[i+1][j] += arr[i][j];
            arr[i+1][j+1] += arr[i][j];
        }
    }
    return arr;
}

 

  이후 문제에서 제시된 r, c, w를 입력으로 받아서 반복문을 통해 원하는 결과를 구해주면 된다. 반복문이 상당히 복잡해보이는데, 그냥 R번째 줄에서 C부터 1개를 더해주고, R+1번째 줄에서는 C부터 2개를 더해주고,... 이걸 W번 해주면 된다.

int sum = 0;
for (int i = r, k = 0; k < w; i++, k++) {
    for (int j = c; j <= c+k; j++) {
        sum += arr[i][j];
    }
}
System.out.println(sum);

 

 

 

---

 

코드 : github

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

public class Main {
    private static final int LIMIT = 30;
    private int[][] getPascalTriangle() {
        int[][] arr = new int[LIMIT+1][];
        for (int i = 1; i <= LIMIT; i++) {
            arr[i] = new int[i+1];
        }
        arr[1][1] = 1;
        for (int i = 1; i < LIMIT; i++) {
            for (int j = 1; j <= i; j++) {
                arr[i+1][j] += arr[i][j];
                arr[i+1][j+1] += arr[i][j];
            }
        }
        return arr;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] arr = getPascalTriangle();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());
        int sum = 0;
        for (int i = r, k = 0; k < w; i++, k++) {
            for (int j = c; j <= c+k; j++) {
                sum += arr[i][j];
            }
        }
        System.out.println(sum);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}