[알고리즘] Swift -백준 #1010(다리 놓기) -DP

문제링크

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

1010번: 다리 놓기

 

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력

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

출력

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

예제 입력 1 

3
2 2
1 5
13 29

예제 출력 1 

1
5
67863915

 

 

 

 

 

분석

강에 다리를 지으려고 한다. 

강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 

서쪽에 n개의 사이트, 동쪾에는 m개의 사이트 (n <= m)

서쪽의 사이트에서 동쪽의 사이트를 다리로 연결하려고 한다. 한 사이트에는 한 개의 다리만 연결할 수 있다.

다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트는 모두 연결해야한다.

다리는 겹칠 수 없을 때 다리를 지을 수 있는 경우의 수를 구하는 문제

 

풀이 과정

t = 테스트 케이스

n = 서쪽의 사이트, m = 동쪽의 사이트

 

n개의 반복을 통해 n개의 다리를 만들어야한다.

 

먼저 규칙을 찾기 위해서 대입을 해보면

일단 초기값은 n =1이면 m의 값과 상관없이 1의 값이 나온다.

n = 1일 때 m = 1 -> 1 m = 2 -> 2 m = 3 -> 3 m = 4 -> 4

n = 2일 때 m = 2 -> 1 m = 3 -> 2+1 m = 4 -> 3+2+1 m = 5 -> 4+3+2+1

n = 3일 때 m = 3 -> 1 m = 4 -> 2+1+1 m = 5 -> 3+2+1+2+1+1 m = 6 -> 4+3+2+1+3+2+1+2+1+1

식을 보면 dp[n][m]이라고 할때,

dp[3][5] = dp[2][4] + dp[2][3] + dp[2][2]

dp[3][6] = dp[2][5] + dp[2][4] + dp[2][3] + dp[2][2]

이러한 규칙을 가진다.

dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] ... dp[i-1][i-1]

 

먼저 초기값을 세팅해준다. n=1일 때 

var map = Array(repeating: Array(repeating: 0, count: 30), count: 30)
for i in 0..<30 {
    map[1][i] = i
}

 

n = 2일 때부터 반복을 해준다.

m은 n과 같거나 커야하기 때문에 j의 범위를 i부터 30까지로 정한다.

j-1 부터 i-1 까지 -1씩 줄어들면서 반복한다.

 

 

for i in 2..<30 {
    for j in i..<30 {
        for k in stride(from: j-1, through: i-1, by: -1) {
            map[i][j] += map[i-1][k]
        }
    }
}

n과 m의 범위가 30까지이니까 30까지의 계산을 한 후 필요한 위치의 수를 꺼내서 출력만 한다.

 

 

풀이 1

import Foundation

var map = Array(repeating: Array(repeating: 0, count: 30), count: 30)
for i in 0..<30 {
    map[1][i] = i
}

for i in 2..<30 {
    for j in i..<30 {
        for k in stride(from: j-1, through: i-1, by: -1) {
            map[i][j] += map[i-1][k]
        }
    }
}

let t = Int(readLine()!)!
for _ in 0..<t {
    let input = readLine()!.split(separator: " ").map{ Int($0)!}
    let (n, m) = (input[0], input[1])
    print(map[n][m])
}

 

결과

 

 

풀이 2

재귀를 이용하여 반복한 값을 더해주어 배열에 저장하였다.

위에는 범위 전부를 먼저 계산했다면 이번 방법은 입력한 범위까지만 계산을 한다.

import Foundation

var map = Array(repeating: Array(repeating: -1, count: 30), count: 30)
for i in 0..<30 {
    map[1][i] = i
}

func dp(n: Int, m: Int) -> Int {
    if map[n][m] == -1 {
        var sum = 0
        for i in 1..<m {
            sum += dp(n: n-1, m: i)
        }
        map[n][m] = sum
    }
    return map[n][m]
}
    
let t = Int(readLine()!)!
for _ in 0..<t {
    let input = readLine()!.split(separator: " ").map{ Int($0)!}
    let (n, m) = (input[0], input[1])
    print(dp(n: n, m: m))
}

원하는 범위까지만 계산해서 시간이 줄어들었을 줄 알았는데 예상외로 시간은 똑같이 걸렸다.

아마 테스트에 최대 수가 들어있어서 그런건가보다..(?)

 

 

---

📂  정리

이번 문제는 점화식은 빨리 풀었는 데

반복문에서 조금 헷갈려서 런타임에러나 났다.

2번 방법에서 sum 변수에 저장해서 반환하여 넣어줘야되는 것을 생각하는 게 오래걸렸다... (바보...)