[코틀린] 백준 1010번 다리놓기

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

1010번: 다리 놓기

풀이

서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다.
다리끼리는 겹칠 수 없고 최대한 많이 지으려 한다.


우리는 일단 케이스에 대하여 분리하여야 한다.
n이 1이라면 -> 그냥 m가지가 나오고
n == m 이라면 -> 1가지
라는 경우의 수가 주어진다.

이 외에 대하여 우리는 진행을 해볼 것이다.

dp[i][1] = i의 값과 dp[i][i] =1을 가지는
dp[n][m] = dp[i-1][j-1] + dp[i-1][j] 가 되는것이다.

가 풀면서 썼던 풀이이고 이거에 대한 설명을 하게 된다면

우리가 왼쪽에 4개 오른쪽에 6개씩 있다면 결국 이것은 우리가 고등학교 수업시간에 배운조합의 문제라는 것을 알고 있을것이다.

 

큰쪽에서 적은쪽의 갯수 만큼 고르는 문제이다.

 

nCr을 이용하여 구하는 nCr = (n-1)C(r-1) + n-1Cr 이 되는 것이다.

우리가 문제에서 주의해야 할점은

nC1 = n이고 , nCn = 1 인데 dp로 구할때 더하기를 할때 따로 미리 초기화를 진행해줘야 한다는 점이다.

 

 

 

근데 이런식의 풀이가 나는 생각하고 있었는데 계속 문제를 풀어도 틀리다고 나온다..라고 생각했는데

풀이

fun main(){
    var dp = Array(31){LongArray(31)}
    var t : Int = readLine()!!.toInt()

    for(i in 1 .. 30){
        dp[i][1] = i.toLong()
        dp[i][i] = 1
    }
    for(i in 1.. 30){
        for(j in 2 until i){
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        }
    }

    for ( i in 0 until t){
        // map{...} 와 함게 toInt() 또는 toIntOrNull() 정수로 변환하는 함수
        //var (N,M) = readLine()!!.split(' ').map{it.toInt()}
        //forEach를 이용하여 정수 어레이를 문자열로 가능 -> 이것도 하기
        var (n,m) = readLine()!!.split(' ').map{it.toInt()}
        print("${dp[m][n]}\n")
    }

}

마지막에 \n 개행을 안해줘서 계속  틀려서 함수를 고치는 바보짓을 했다.. 이런 바보