[Java] 백준 1010번: 다리 놓기

hansung's·2024년 3월 24일

문제 url:
다리 놓기

문제

🤔 문제 알아보기

강을 기준으로, 서쪽과 동쪽에 다리를 놓을려고 한다.
서쪽(N)은 동쪽(M)보다 다리 개수가 적거나 같다고 하는데, N<= M
또한, 다리를 놓을때는 해당 다리가 절대 겹치면 안된다고 한다.
그 다음. 하나의 구역에는 반드시 하나의 다리만 설치할 수 있다.
이를 그림을 포현하면

자, 문제 조건에 대해 알아보았다. 그러면 문제를 어떻게 풀 수 있을까 고민을 해보자

먼저, 위의 조건에 따라 N <=M을 가진다고 한다. 여기서, 다리를 지을 수 있는 모든 경우의 수를 구한다는 말은 M개의 포인트 중에 N개만큼 다리를 놓는 경우일 것이다.

그리고, 하나의 구역에는 반드시 하나의 다리만 설치할 수 있다. 즉, 중복되는 다리가 있으면 안되는 얘기다.

그렇다!! 우리는 조합을 떠올릴 수 있다.
조합은 서로 다른 N개의 원소중 r개를 뽑는데, 이를 순서와 상관없이 중복없이 뽑는 경우의 수를 의미한다.

여기서 우리는 아까 다리가 교차하면 안된다는 조건을 생각할 수 있다.
근데, 조합은 설명했듯 순서와 상관이 없다고 했다.

이 말은 우리가 1, 3, 4 (올바른 조건) 에 다리를 놓든 1, 4, 3 (교차되어 틀린 조건) 에 놓든 4, 1, 3 (교차되어 틀린 조건) 다 하나의 경우의 수로 본다는 얘기이다.

한 마디로 뽑는 순서와 상관없이 해당 숫자가 나오면, 하나로 보는 것이다.
또한 중복이 없다는 조건에서
우리는 1, 3, 3 경우 역시 조합공식에서는 해당 안된다는 것을 볼 수 있는 것이다.

조합에 더 살펴보자면, 아래의 링크를 확인하면 된다
[조합론]이항계수(Binomial_coefficient)는 무엇? 그리고 알고리즘 구현법에 대해 알아보자

조합의 공식을 간략히 먼저 살펴보면 아래와 같다.

{\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.

하지만, 해당 공식을 사용하게 되면 일일이 팩토리얼로 수치를 구해줘야 하며 분수이기 때문에 나누는 작업도 진행해야 한다.
그래서 조합의 다른 공식을 사용하고자 한다.

{n \choose k }={n-1 \choose k-1 }+{n-1 \choose k }

해당 공식을 사용하면, $nCk$ 의 값을 구할 수 있을 것이다.

추가로, 위의 공식(파스칼의 공식)을 사용할 때에는 다음 조건을 기억해야 선행으로 기억해야 한다.

{0 \choose 0}=1}, {\displaystyle {n \choose 0}=1} ,{\displaystyle {n \choose n}=1

자, 이를 코드화 시켜보자

🐱‍👤 실제 코드

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

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

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

            // n <= m
            int n = Integer.parseInt(st.nextToken()); // 서쪽
            int m = Integer.parseInt(st.nextToken()); // 동쪽

            System.out.println(factorial(m, n));
        }
    }
    static int factorial(int n, int r) {
        
        if(n == r || r == 0) {
            return 1;
        }

        return factorial(n-1, r-1) + factorial(n-1, r);
    }

}

엥 안되네????....

자 우리는 문제 조건을 다시 꼼꼼하게 읽어보면 시간제한이 0.5초이다.
그렇다면 필자계산법에 의하면 1초가 1억번 연산횟수를 가지니깐... 5천만번인데?

필자가 그래서 해당 factorial 메서드 연산 호출을 계산해보니깐.
문제 tc인 13 29 를 입력했을 때 대략 1억 3천만번의 호출을 기록하였다.
그렇다. 1초를 줘도 현재 형태를 풀 수 없다.

그러면 어떻게 해야 시간 제한이 걸리지 않을까??

🐱‍👤 실제 코드(DP 사용)

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

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

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

            // n <= m
            int n = Integer.parseInt(st.nextToken()); // 서쪽
            int m = Integer.parseInt(st.nextToken()); // 동쪽

            System.out.println(factorial(m, n));
        }
    }
    static int factorial(int n, int r) {

        if(dp[n][r] > 0) {
            return dp[n][r];
        }

        if(n == r || r == 0) {
            return dp[n][r] = 1;
        }

        return dp[n][r] = factorial(n-1, r-1) + factorial(n-1, r);
    }

}

먼저, 코드부터 공개를 하겠다. 그러면 왜 이렇게 짜는 건가요??

그 이유는 재귀함수의 문제이다.
재귀함수를 사용해 부분 문제를 풀 때, 중복된 부분 문제도 다시 풀어야 해서 함수의 성능이 떨어지는 문제가 발생한다.

 static int factorial(int n, int r) {
        
        if(n == r || r == 0) {
            return 1;
        }

        return factorial(n-1, r-1) + factorial(n-1, r);
    }

틀린 코드를 이용해 한번 풀어보겠다.

우리가 만약 $5C3$ 을 푼다고 가정하자, 그럼 첫 호출때
$4C2$ + $4C3$ 값을 재귀할 것이다. 이를 또 계산하면
( $3C1$ + $3C2)$ + ( $3C2$ + $3C3$ ) 값을 재귀할 것이다.

여기서 $3C2$ 가 중복되는 것을 볼 수 있다. 이것을 중복처리 하지 않으면,
해당 값이 n==r이 되거나 r ==0이 될 때까지 계속 재귀하게 될 것이다.

이때 우리는 Memorization(메모리제이션)이라는 최적화를 적용해야 하는 것이다.

Memorization이란?
이전에 계산된 값을 메모리(cache)에 저장하여 동일한 계산을 수행하지 않도록 하는 기술

※메모리제이션은 DP(Dynamic Programming - 동적 계획법)에서 전체 실행 속도를 빠르게 해주는 기술인데
DP란 큰 문제를 작은 문제로 나누어 푸는 알고리즘을 일컫는 말로,
여기서는 자세히 다루지 않고, 새로운 세션에서 한번 정리를 해보겠다.

자 다시 본론으로 돌아와서, 재귀함수를 이용하면 발생할 수 있는 overhead를 줄이기 위해 memorization을 사용하게 되면
$3C2$ 와 같이 중복된 계산을 하지 않아, 동일한 값이 여러번 호출되어도 상관 없을 뿐더러 연산에 큰 이점이 생긴다.

🙄 코드 해석 및 풀이

 dp = new int[30][30];

dp는 2차원 배열로 생성해, n과 r의 값을 받아 해당 배열에 값을 담을 것이다.
문제 조건에 따르면 N, M (0 < N ≤ M < 30)이 주어진다고 했기 때문에 30만큼 크기를 준 것이다.

 static int factorial(int n, int r) {

        if(dp[n][r] > 0) {
            return dp[n][r];
        }

        if(n == r || r == 0) {
            return dp[n][r] = 1;
        }

        return dp[n][r] = factorial(n-1, r-1) + factorial(n-1, r);
    }

다음은 factorial 메서드를 재귀호출 하는 것인데,
먼저 dp배열 값이 0보다 크다는 것은, 값이 존재한다는 것으로
현재 $nCr$ 에 대한 계산이 끝났다는 말이다.

그래서 이를 이용해 반복적인 재귀호출을 하지 않고 바로 값을 계산할 수 있는 것이다.

그 후 n == r || r ==0 은, 조합 공식에 있는 규칙으로, 아래 공식을 처리한 것이다.

{0 \choose 0}=1}, {\displaystyle {n \choose 0}=1} ,{\displaystyle {n \choose n}=1

또한 해당 공식을 통해, 재귀함수의 궁극적 값이 1로 구한다는 의미이기도 하다.

끝으로, dp 배열에 현재 $nCr$ 값에 재귀호출 후 더한 값을 저장하여
해당 값을 return 받거나 혹은 반복을 줄이기 위한 값으로 메모리에 저장할 수 있다.

🤢 회고

해당 문제를 풀 때 첨에는 순열을 생각했었다. 하지만, 다리가 교차되면 안되는 점을 해결하지 못하여 조합을 떠올리지 못했는데,
조합은 순서와 상관없이 한다는 것이 곧 다리가 교차되면 안되는 조건과 부합하다는 것을 추후 포스팅 된 글을 보면서 알게되면서 문제를 풀 수 있었다.

그런 다음 재귀함수의 문제점과 이를 해결하기 위한 DP방식의 memorization을 알아보면서, 새롭게 공부할 것을 찾았고 이를 나중에 포스팅 해보도록 하겠다.