I am visible

homepage

contact

contents

home > algorithm > baekjoon > [baekjoon] 다리 놓기 (백준 1010 java 풀이)

[baekjoon] 다리 놓기 (백준 1010 java 풀이)
algorithm 2024-11-25 - -
algorithm baekjoon step19

intro : 최적화를 해서 문제를 풀어보자.

백준 문제링크

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

문제 풀이1 (BigInteger를 이용한 풀이 160ms)

import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        // 반복 횟수 변수 선언
        int forCount = Integer.parseInt(br.readLine());
        // 반복 횟수만큼 반복문 실행
        for (int i = 0; i < forCount; i++) {
            // 입력값이 13 29 이런식으로 라인별로 들어오기에 StringTokenizer 객체 생성
            StringTokenizer st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());

            // 문제에서 주어진 조건은 두번쨰로 들어온 값이 첫번쨰로 들어온 값보다 크거나 같음
            BigInteger value1 = factorial(second);
            BigInteger value2 = factorial(second - first);
            BigInteger value3 = factorial(first);

            // 곱하기, 나누기 연산
            BigInteger multiply = value2.multiply(value3);
            BigInteger divide = value1.divide(multiply);
            sb.append(divide).append("\n");
        }

        // bw로 출력하기 위해 sb를 문자열로 변환 후 write
        bw.write(sb.toString());
        bw.flush();

        // 자원 반납
        bw.close();
        br.close();
    }

    public static BigInteger factorial(int n) {
        // factorial 메소드를 실행하기 위한 각 변수 BigInteger 타입으로 선언
        BigInteger result = BigInteger.ONE;
        BigInteger inputN = BigInteger.valueOf(n);
        BigInteger zero = BigInteger.ZERO;
        BigInteger one = BigInteger.ONE;
        
        // BigInteger는 compareTo 메소드로 비교 
        while (inputN.compareTo(zero) > 0) {
            result = result.multiply(inputN);
            inputN = inputN.subtract(one);
        }
        return result;
    }
}

문제 해석1

문제의 내용의 주된 포인트는 왼쪽 사이트의 지점에 모두 다리가 건설이 되어야 한다 라는 점이 포인트다. 그말은 즉슨 오른쪽 다리에서 왼쪽다리는 무조건 선택해서 다리를 지어야 하기에, 중복되지않게 다리를 지으려면 오른쪽 다리의 사이트 포인트 중에서 왼쪽 다리의 사이트 포인트 만큼의 조합의 개수를 구하면 된다는 말로 귀결된다. 결국 이 문제 또한 조합의 갯수를 구하는 문제이며 해당 문제를 이해했다면 구현 로직으로 넘어가면 된다.

구현 로직에서 함정이 있는데, 보통 아무리 큰 값을 계산하더라도 long 타입으로 어느정도는 계산이 되는데, 30!을 계산하려면 long 을 통해 계산을 할 수 없다.(아래 그림을 참고하면 30!의 값이 얼마나 큰 값인지 알 수 있다.) 그렇다면 그보다 더 큰 데이터 범위를 담을 수 있는 객체를 사용해야 하는데 해당 문제를 풀기위해 BigInteger 타입을 사용하여 계산해 주었다.

image1

문제 풀이2 (최적화를 통한 풀이 112ms)

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        // 반복 횟수 변수 선언
        int forCount = Integer.parseInt(br.readLine());
        // 반복 횟수만큼 반복문 실행
        for (int i = 0; i < forCount; i++) {
            // 입력값이 13 29 이런식으로 라인별로 들어오기에 StringTokenizer 객체 생성
            StringTokenizer st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());
            // 조합을 계산하는 최적화 메소드 호출 
            long result = combination(second, first);
            sb.append(result).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    public static long combination(int second, int first) {
        // 결과값 변수 1 선언
        long result = 1;
        for (int i = 0; i < first; i++) {
            // 분자 계산
            result *= second - i;
            // 분모 계산
            result /= i + 1;
        }
        return result;
    }
}

문제 해석2

위 코드에서 팩토리얼의 불필요한 연산과정을 줄이고 BigInteger 타입을 사용하지 않더라도 long 타입으로 연산을 할 수 있는 방법이 존재한다. 문제풀이1에서는 현재 순차적으로 계산을 진행하다보니, 큰 결과값이 도출되어 어쩔수 없이 BigInteger을 사용했는데 다음과 같은 방법을 사용하면 long 타입으로도 문제를 해결 할 수 있다.

먼저 어떻게 중복된 연산과정을 줄였는지 아래 이미지를 보면서 알아보자.

image2

만약 10개의 카드중에 3개의 카드의 조합을 구하는 문제가 있다면 위 계산을 적용할 것이다. 근데 잘 생각해보면 분자와 분모에서 중복되어 약분이 되는 부분이 있는데, 현재 상황에서는 아래 이미지처럼 바로 7!이 약분되어 나머지 부분만 연산을 진행하면 최적화된 계산을 진행할 수 있다.

image3

해당 내용을 정리하자면 결국 10개의 카드중에 3개의 카드를 뽑는 조합을 구하는 문제를 풀기위한 연산은 10~8 까지의 팩토리얼 연산과(분자) 1~3까지의 팩토리얼 연산(분모)만 하면 최적화된 결과를 구할 수 있음을 알 수 있다.