[BOJ] 1010_다리 놓기 재해결

다리 놓기

링크: https://www.acmicpc.net/problem/1010

이전에 단순 코드로 해결한 적이 있었다. 링크
하지만, 시간제한이 들어가며 O(n^2)의 코드는 재채점 되어 실패가 되었다.

그래서 이를 다시 해결하기로 했고, 다음의 정답을 유추했다.
서쪽에 있는 점들이 선택한 동쪽 점들은 그 선이 교차가 되면 안되기에 서쪽의 있는 점들은 동쪽에 있는 점들에 의해 의존됨을 알 수 있다.
이 말은 동쪽에 있는 점들을 서쪽의 점 개수만큼 정하게 되면 서쪽은 자연스레 그 점들에 의해 배치된다는 것을 의미한다.
그렇다면, 동쪽의 점들 m개 중에서 서쪽의 점들 n개를 선택하면 된다.
이는 조합 공식으로 해결할 수 있다.

따라서, 조합의 코드를 해결하는데, n!/r!이므로 이를 아래와 같이 구현했다.

• 정답 코드

import java.math.BigDecimal

class Main {
    companion object{
        fun combination(n: Int, r: Int): BigDecimal{
            var bigN = (1).toBigDecimal()
            var bigR = (1).toBigDecimal()

            (0 until r).forEach{
                bigN *= (n.toBigDecimal() - it.toBigDecimal())
                bigR *= (r.toBigDecimal() - it.toBigDecimal())
            }

            return bigN / bigR
        }

        @JvmStatic
        fun main(args: Array<String>){
            val c = readln().toInt()
            for(i in 0 until c){
                val item = readln().split(' ')

                println(combination(item[1].toInt(), item[0].toInt()))
            }
        }
    }
}

 

---

 

너무 빨리 풀어 조합 구하는 공식을 다른 방식으로 구현해보고자 한다.
조합은 다음의 공식이 성립한다.

nCr = (n-1)C(r-1) + (n-1)Cr

증명은 위키백과에서 가져왔다.

• 증명: n명중 B라는 사람을 우선 빼놓고 생각하자. 그렇다면
  • n명중 A그룹에 들어갈 k명을 고르는 가짓수 = B를 무조건 A그룹에 포함하는 경우 + B를 무조건 배제하는 경우 = n-1명 중 k-1명 선정 + n-1명 중 k명 선정을 하는 가짓수이다.

위의 공식을 재귀함수를 이용해서 구현하면 손쉽게 구현할 수 있다.
다만, 기존에 구했던 데이터들은 다시 재사용 될 수 있다.
그렇기에 dp라는 배열에 이전에 계산했던 데이터라면, 그 값을 리턴해주고 종료한다.
또한, 해당 함수의 종료 조건은 n과 r이 같거나, r이 0에 도달했을 경우 그 값은 1로 마무리 된다.
구현한 코드를 확인하자.

• 정답 코드

import java.math.BigDecimal

class Main {
    companion object{
        private const val dpSize = 31
        val dp = Array(dpSize) {Array(dpSize){(0).toBigDecimal()}}

        fun combinationWithDP(n: Int, r: Int): BigDecimal{
            if(dp[n][r] != (0).toBigDecimal()) return dp[n][r]
            if(n == r || r == 0) return (1).toBigDecimal()

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

        @JvmStatic
        fun main(args: Array<String>){
            val c = readln().toInt()
            for(i in 0 until c){
                val item = readln().split(' ')

                println(combinationWithMemoization(item[1].toInt(), item[0].toInt()))
            }
        }
    }
}