[코딩테스트 챌린지] 백준 1010 다리 놓기 (java)

문제

 

문제 탐색하기

1. 다리를 지을 수 있는 조건 이해하기

2가지 조건이 있습니다. 한 사이트에는 한 개의 다리만 지을 수 있다는 것과 서로 다른 다리가 겹치면 안된다는 조건이 있습니다.

입력받는 N과 M 값을 통해서 M개 중에서 N개를 선택해서 다리를 지어야한다는 것을 통해 조합공식을 활용하면 된다는 것을 알 수 있습니다.

 

조합이란? 

서로 다른 n개에서 순서에 상관없이 r개를 고르는 것을 말합니다. 

다리가 겹치면 안된다는 조건을 조합의 개념을 통해 만족시킬 수 있습니다.

1		1		1) 1 -> 3 / 2 -> 2 (3,2)
2		2		2) 1 -> 2 / 2 -> 3 (2,3)
		3

 

위 처럼 N=2, M=3 인 것을 예시로 들면 첫번째 케이스는 다리가 겹치게 되고 두번째 케이스는 겹치지 않지만 결국 M 중 어떤 것을 선택하는 지는 2,3으로 동일합니다. 이처럼 순서에 상관없이 r개를 고르는 조합의 특성을 활용한다면 문제를 풀 수 있을 것입니다.

 

2. 조합의 특성 살펴보기

 

조합은 위의 특성이 있습니다. 이 특성들을 사용하여 문제를 풀도록 하겠습니다.

 

코드 설계하기

1. 배열 선언 
2. 테스트케이스 수 T 입력
3. N, M 입력
4. M개 중에서 순서에 상관없이 N개를 선택하는 조합의 특성을 활용한 메소드 호출
   1. 선언된 배열에서 저장된 값이 있으면 return
   2. n==r 또는 r==0 인 경우는 조합공식에 따라 1리턴
   3. nCr = n-1Cr-1 + n-1Cr : 조합공식에 따라 재귀호출 
5. 출력

 

정답 코드

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

public class Bridge {

	// 1. 배열 선언
    static int[][] bridge = new int[30][30];

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        // 2. 테스트케이스 수 입력
        int T = Integer.parseInt(reader.readLine());

        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<T; i++){
            st = new StringTokenizer(reader.readLine());

            // 3. n과 m 입력
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            // 4. m개 중에서 n개 선택 --> 조합의 특성을 활용한 메소드 호출
            sb.append(makeBridge(m, n)).append("\n");
        }
        
        // 5. 출력
        System.out.println(sb.toString());
    }

    private static int makeBridge(int n, int r) {

        // 4-1. 저장된 값이 있으면 return
        if(bridge[n][r] > 0) {
            return bridge[n][r];
        }

        // 4-2. n==r이 동일하거나 r=0일 경우는 1이기에 해당 값 세팅
        if(n == r || r == 0) {
            return bridge[n][r] = 1;
        }

        // 4-3. nCr = n-1Cr-1 + n-1Cr
        return bridge[n][r] = makeBridge(n-1, r-1) + makeBridge(n-1, r);
    }
}