백준_1010

🚨오늘의 학습🚨

🎯 조합 + DP(BottomUp->반복문)

🗝️ 동쪽 사이트 중 서쪽 사이트 개수만큼 선택
🗝️ 다리가 겹치지 않아야 함 -> 선택한 사이트의 순서 상관X
※ 조합(동쪽사이트C서쪽사이트) ※

⭐️파스칼의 삼각형⭐️
✅ 조합의 메모제이션 미리 초기화 가능

🔸BottomUp(반복문-for)

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int caseCnt = Integer.parseInt(br.readLine());
        
        long[][] dp = new long[31][31]; // 최대 30C30까지 계산 가능

        // 파스칼의 삼각형 초기화
        for (int n = 0; n <= 30; n++) {
            dp[n][0] = 1;
            dp[n][n] = 1;

            for (int r = 1; r < n; r++) {
                dp[n][r] = dp[n - 1][r - 1] + dp[n - 1][r];
            }
        }
        
        //BottomUp
        for (int i = 0; i < caseCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int west = Integer.parseInt(st.nextToken());
            int east = Integer.parseInt(st.nextToken());

            System.out.println(dp[east][west]);
        }
    }
}

🔸TopDown(DP+DFS)

 static long[][] dp = new long[31][31];
    static long[] resultArr;

    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int caseCnt = Integer.parseInt(st.nextToken());

        resultArr = new long[caseCnt];

        for (int x = 0; x < 30; x++) {
            Arrays.fill(dp[x], -1L);
        }

        for(int i=0; i<caseCnt; i++){
            st= new StringTokenizer(br.readLine());

            int westCnt=  Integer.parseInt(st.nextToken());
            int eastCnt = Integer.parseInt(st.nextToken());

            resultArr[i] = dfs(westCnt,eastCnt);

        }

        for (long l : resultArr) {
            System.out.println(l);
        }


    }

    public static long dfs(int west,int east){
        if(west==0 || west==east){
            // 메모제이션 기본값 초기화
            // 파스칼의 삼각형 좌/우 =1
            return dp[east][west] = 1;
        }

		
        // 메모제이션 값이 있다 != -1
        if(dp[east][west]!=-1){
            return dp[east][west];
        }

         
        // 파스칼의 삼각형 규칙
        
        // 메모제이션 값이 없다 == -1
        // dfs 재귀로 메모제이션 값을 찾아가기
        return dp[east][west] = dfs(east-1,west-1)+dfs(east-1,west);

    }