백준1010번 다리 놓기 - JAVA

안녕하세요 놀이방 사장입니다.

 

이번 포스팅은 백준

1010번 다리놓기 포스팅입니다.

1010번: 다리 놓기

이 문제는 조합의 갯수를 구하면 되는 문제인데

그냥 구현하면 시간초과가 납니다..

저처럼.. 시간 초과 나는 코

package me.joyeonggyu;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.*;

public class Main{
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        for(int i=0; i<n; i++){
            String[] arr = br.readLine().split(" ");
            int N = Integer.parseInt(arr[0]);
            int M = Integer.parseInt(arr[1]);
            bw.write(String.valueOf(Combination(M,N)));
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }

    public static int Combination(int n , int r){
        int answer = 0;
        if(n==r || r==0){
            answer = 1;
        }else{
            return Combination(n-1,r-1) + Combination(n-1,r);
        }
        return answer;
    }
}

 

인터넷에 쳐보니 메모이제이션이라는 기법을 사용해야하더군요

 

 

메모이제이션이란??

- 동일한 계산을 반복 할 때 이전에 계산한 값을 메모리에 저장해놓고 필요시 사용하여 반복적인 연산을 제거하는 기술이라고 합니다.

 

코드

package me.joyeonggyu;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.*;

public class Main {

    private static int[][] dp = new int[31][31];

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

        int n = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n; i++) {
            String[] arr = br.readLine().split(" ");
            int N = Integer.parseInt(arr[0]);
            int M = Integer.parseInt(arr[1]);
            bw.write(String.valueOf(Combination(M, N)));
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }

    public static int Combination(int n, int r) {
        // 이미 계산된 값
        if (dp[n][r] > 0) {
            return dp[n][r];
        }
        // 원소의 갯수가 조합의 갯수와 동일하거나 0일 경우
        else if (n == r || r == 0) {
            return dp[n][r] = 1;
        } else {
            return dp[n][r] = Combination(n - 1, r - 1) + Combination(n - 1, r);
        }
    }
}

아까랑 달라진 점은 배열에 계산한 값들을 넣어서 연산을 줄였습니다.

 

이게 위에 코드랑 가장 큰 차이점인듯

 

알고리즘하면서 많이 배웁니다.