[백준 자바] 1010번 다리놓기 (조합/dp)

 

* 시간 제한이 매우 짧다 0.5초 

* M개 중에서 N개를 조합하는 문제 (nCr)

* 조합의 경우의 수 구하기..! 

 

오~~ 저번에 봤던 거 같은데 하면서 풀었다. 

그런데 시간 초과가 계속 떴다. 이유가 있었지 암...

 

첫번째 풀이) (바보풀이임 따라하지 마셈)

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

//다리 놓기 실버5
public class Main {
    public static void main(String[] args) throws IOException {
        //테스트 케이스의 수 T
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        // 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M
        for(int i=0; i<T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            // N개만큼 다리를 지으려고 할 때 다리를 지을 수 있는 경우의 수를 구한다.
            // mPn
            System.out.println(combination(M,N));
        }


    }
    public static int combination(int n, int r){ //nCr 경우의수 구하기
        if(n==r||r==0) {
            return 1;
        } else {
            return combination(n - 1, r - 1) + combination(n - 1, r);
        }
    }
}

 

 

저번에 공부했던 코드를 생각해냈다.

 

그림까지 그려가며 이해해보았던...코드...

근데 그렇게 썼는데 왜 안될까 ? ? 

알고리즘 초짜의 마인드.... ㅠ ㅠ 

combination 메서드 안에서 또 combination 함수를 불러낼 때 마다 새로이 재귀함수를 호출하는 것이다. 

왜냐하면 따로 저장해두는 공간도 없고, 그런 로직도 없으니까  !!! 

 

그래서 쓰는 것이 동적 계획법이라고 한다

4C2에서도 3C2가 필요하고, 4C3에서도 내부를 보면 3C2가 필요하다... 그럼 한번만 계산해서 저장해두고 그때마다 꺼내쓰면 더 빠르잖아!!!~~~~~

 

 

ㅇㅋㅇㅋ

재도전 해보겠습니당

 

동적 계획법(dp)에 대해서는 따로 정리해두었다. 요기

https://hehesim.tistory.com/entry/DPDynamic-Programming

 

 

두번째 풀이)

동적 계획법의 

1) 탑다운 / 재귀적 풀이로 풀어보았다.

** 결과를 저장할 배열 2차원 배열 만들기

** 이미 계산된 값이면 바로 결과값을 호출하기

** 나머지 같음. 저장 해주는 로직만 추가하기

 

//다리 놓기 실버5
public class Main {
    private static final int[][] dp = new int[30][30]; //저장할 공간 생성! M,N이 30미만이므로 크기 지정가능 

    public static void main(String[] args) throws IOException {
        //테스트 케이스의 수 T
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();
        // 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M
        for(int i=0; i<T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            // N개만큼 다리를 지으려고 할 때 다리를 지을 수 있는 경우의 수를 구한다.
            // mPn
            sb.append(combination(M, N)).append("\n");
        }
        System.out.println(sb);
        br.close();
    }
    
    public static int combination(int n, int r){
        //이미 계산된 값일 경우 (이미 내가 저장을 했다!? 그렇다면 초기값인 0은 아니겠지...)
        if (dp[n][r]>0) { // 저장값이 0보다 크면
            return dp[n][r]; // 그 저장된 값을 리턴
        }
        else if(n==r||r==0) { //원소의 개수가 조합의 갯수와 동일하거나 0일 경우
            return dp[n][r] =1; // 그 자리에 1저장
        } else { 
            return dp[n][r] = combination(n - 1, r - 1) + combination(n - 1, r); // 재귀함수 활용
        }
    }
}

 

풀어보는 김에 다르게도 풀어보자.

 

세번째 풀이)

동적 계획법의 

2) 바텀업 / 반복적 풀이로 풀어보았다. 

** 똑같이 결과를 저장할 배열 2차원 배열 만들기

** 초기값 저장해주기. (n==r, r==0일 때/ 그 외는 nCr = n-1Cr-1 + n-1Cr 공식 활용)

** 저장된 값 불러들이기만 하면 끝

//다리 놓기 실버5
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();

        int[][] dp = new int[30][30]; // 똑같이 저장공간 만들어주기 

		//초기값부터 설정!!! 
        for(int i=1; i<30; i++) { // n==r일 때와 r==0일때 1로 설정
            dp[i][i] = 1; //n==r
            dp[i][0] = 1; //r==0
        }

        // 그 외에는 nCr = n-1Cr-1 + n-1Cr 규칙 사용하여 계산하여 저장
        for(int i=2; i<30; i++) {
            for(int j=1; j<30; j++) {
                dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
            }
        }

		//저장 한 후 결과값 도출하는 로직
        for(int i=0; i<T; i++) {
            StringTokenizer 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);
    }
}

 

 

두번째와 세번째는 거의 비슷했다 결과~

위: 바텀업 / 아래: 탑다운

 

하루에 한 문제라도 풀자

아주 쉬운 문제라도... 꾸준함이 답이다

비슷한 유형들을 뽀개보자