[백준/JAVA] 15489번: 파스칼 삼각형

📖 문제

15489번: 파스칼 삼각형

 

 

💡  풀이 방식

• 조합 (DP)

파스칼 삼각형을 모두 왼쪽으로 밀었다고 생각하고 2차원 배열을 채운다. 맨 왼쪽 줄(= 0번째 열) 과 행=열인 칸은 값을 1로 채운다.

나머지 (i, j) 위치의 칸은  왼쪽 위 칸 (i-1, j-1)과 바로 윗 칸 (i-1,j)의 합으로 채운다.

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

 

점 (R,C)부터 길이가 W인 삼각형의 합을 구한다. 이 때 삼각형 모양으로 범위를 제한하기 위해 변수 tmp를 활용하며, 현재 행 i가 R로부터 얼만큼 길어졌는지 그 값을 사용해 행마다 열 길이의 범위를 제한한다.

 

for(int i = R ; i < R + W ; i++) {
    tmp = i - R;    // j의 길이 범위 제한하기

    for(int j = C ; j < C + W ; j++) {
        if(R <= i && i < R + W && C <= j && j <= C + tmp) {
            sum += dp[i][j];
        }
    }
}

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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[][] dp = new int[R + W][R + W];
        for(int i = 1 ; i < dp.length ; i++) {
            dp[i][1] = 1;
            dp[i][i] = 1;
        }
        
        for(int i = 1 ; i < dp.length ; i++) {
            for(int j = 1 ; j < i ; j++) {
                if(i==j)    continue;
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }
                
        int sum = 0;
        int tmp = 0;    // j의 길이 범위를 삼각형 모양으로 제한하기 위한 변수
 
        for(int i = R ; i < R + W ; i++) {
            tmp = i - R;    // j의 길이 범위 제한하기
            
            for(int j = C ; j < C + W ; j++) {
                if(R <= i && i < R + W && C <= j && j <= C + tmp) {
                    sum += dp[i][j];
                }
            }
        }
        
        System.out.println(sum);
    }
}
 

 

 

➕ 다른 풀이 방식

1) dp식이 다르다! 이것이 훨 깔끔하구먼.. (출처)

for(int i = 0 ; i < W ; i++) {
	for(int j = 0 ; j <= i ; j++) {
    	sum += dp[R + i][C + j];
    }
}

 

 

2) dp 배열 채우는 것부터 합 구하는 것까지 깔끔하다. 담엔 이렇게 풀어야지!

[백준 알고리즘] 백준 15489번 파스칼 삼각형 자바(Java)

---

💦 어려웠던 점

- 한 지점으로부터 길이가 W인 정삼각형을 구할 때 어떻게 저 범위까지만 삼각형으로 가져올 수 있지?에 시간이 좀 걸렸다ㅠ

 

 

🧐 새로 알게 된 내용

파스칼 삼각형의 한 지점으로부터 삼각형 모양 범위로 합을 구할 때는 이렇게 진행하자.

for(int i = 0 ; i < W ; i++) {
	for(int j = 0 ; j <= i ; j++) {
    	sum += dp[R + i][C + j];
    }
}

 

 

1회독	2회독	3회독	4회독	5회독
V