[SWEA] 2005번 - 파스칼의 삼각형 [Java]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5P0-h6Ak4DFAUq

 

[SWEA] 2005번 - 파스칼의 삼각형 [Java]

[SWEA] 2005번 - 파스칼의 삼각형 [Java]

---

1.  아이디어

 

2차원 배열로 파스칼의 삼각형을 표현했을 때 위의 두 원소의 합이 아래 원소가 되는 다이나믹 프로그래밍으로 해결했다.

---

2. 문제풀이

 

위쪽과 왼쪽에 패딩을 준 후 0행 0열을 1로 초기화하면 점화식으로 파스칼의 삼각형을 구할 수 있었다. 이후 순회를 하며 0에서 갱신이 안됐으면 순회를 종료하는 방식으로 출력했다.

---

3. 코드

 

import java.io.*;

public class Solution {
    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(Solution.class.getResourceAsStream("input.txt")));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());

            int[][] dp = new int[1 + N][1 + N];
            dp[0][0] = 1;

            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }
            }

            sb.append("#").append(tc).append("\n");
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (dp[i][j] == 0) break;
                    sb.append(dp[i][j]).append(" ");
                }
                sb.append("\n");
            }
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기