[백준/JAVA] 1010번: 다리 놓기

🔺 문제

1010번: 다리 놓기

 

🔺 코드

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;
        
        // DP 배열 초기화
        long[][] bridge = new long[31][31];
        for(int i = 0 ; i <= 30 ; i++) {
            bridge[i][0] = 1;
            bridge[i][1] = i;
            bridge[i][i] = 1;
        }
        
        // DP 수행
        for(int i = 2 ; i <= 30 ; i++) {
            for(int j = 1 ; j < i ; j++) { // 고르는 수가 전체 개수 넘지 않게
                bridge[i][j] = bridge[i - 1][j] + bridge[i - 1][j - 1]; // 파스칼의 삼각형
            }
        }
        
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        
        while(T --> 0) {
            st = new StringTokenizer(br.readLine()," ");
            int N = Integer.parseInt(st.nextToken());   // 서
            int M = Integer.parseInt(st.nextToken());   // 동
            
            sb.append(bridge[M][N] + "\n");
        }
        
        System.out.println(sb);
        br.close();
    }
}

✅ 해결 아이디어
✔ 조합!
- DP (점화식) : Bottom-UP 방식

 

 

💥 유의사항

• 20! 만 되어도 long 범위를 넘어간다고 함!

 

---

🔺 다른 풀이들

- 재귀로도 푼 방법! (메모이제이션)

[백준] 1010번 : 다리 놓기 - JAVA [자바]

 

---

💬 느낀 점

20!만 넘어도 long 범위를 넘어간다는 것을 기억해두자!

 

 

 

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

 

 

(+ 230703 2회독)

위랑 별 차이 없음

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;
        StringBuilder sb = new StringBuilder();
        
        int[][] dp = new int[31][31];
        for(int i = 0 ; i < 31 ; i++) {
            dp[i][0] = 1;
            dp[i][i] = 1;
            dp[i][1] = i;
        }
 
        for(int i = 1 ; i < 31 ; i++) {
            for(int j = 2 ; j < 31 ; j++) {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            }
        } 
        
        int T = Integer.parseInt(br.readLine());
        while(T --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            
            sb.append(dp[M][N]).append("\n");
        }
        System.out.println(sb);
    }
}
 

 

---

(참고)

[백준/JAVA] 11050번: 이항 계수 1