[백준/Swift] 12101번: 1, 2, 3 더하기 2

 

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

12101번: 1, 2, 3 더하기 2

 

전형적인 백트래킹 문제. 최대한 모든 경우의 수를 보지 않게 하기 위해서 조건들을 넣어줬다.

n을 만들 수 있는 k번째에 오는 경우의 수를 찾아야 하기 때문에

• n을 만들 수 있는지 체크
• k번째에 오는 경우의 수인지 체크

flag의 역할은 k번째 값이 없을 경우 -1을 출력하기 위함 && 경우의 수 줄이기

k번째 경우의 수를 출력한 뒤로는 다음 경우의 수에서 더 깊게 들어갈 필요가 없음

→ if문으로 return 해버려서 깊게 들어가는 for문을 수행하지 않음

 

아래를 보면 flag를 통해 이미 k번째 경우를 찾아서 다음 애들은 깊게 안들어가도록 하는 것을 알 수 있음

 

flag 사용/ flag를 사용하지 않음

 

import Foundation

//input
let nk = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (n, k) = (nk[0], nk[1])
var arr = [Int]()
var cnt = 0
var flag = false

func BT(_ sum: Int) {
    //base condition: 종료 조건
    //이미 결과값이 나왔기 때문에 flag라면 더 이상 깊게 가지 않음 -> 바로 return
    if flag { return }
    if cnt == k { //k번째의 경우의 수 출력 
        print(arr.map{String($0)}.joined(separator: "+"))
        flag = true
        return
    }
    
    //경우 만들기
    for i in 1...3 {
        if sum + i > n { continue } //가지치기. n보다 크면 뒤는 할 필요 없음
        if sum + i == n { cnt += 1 } //n을 만들 수 있는 경우, cnt 증가
        arr.append(i)
        BT(sum + i)
        arr.removeLast()
    }
}
BT(0)
if !flag { print("-1") }

 

 

[다른 사람 코드] - DP

 

내 코드는 12ms, 이 코드는 8m

예전에 DP 기본 문제로 풀었던 방식으로 풀면 되는데, 여기서는 문자열 형식으로 해줘서 조금 헷갈릴 수 있을 거 같다.

// MARK: DP
let inp = readLine()!.split(separator: " " ).map{Int(String($0))!}
let N = inp[0], K = inp[1]

var dp = Array(repeating:[String](),count:11)
dp[1] = ["1"]
dp[2] = ["11","2"]
dp[3] = ["111","21","12","3"]

for i in 4...10 {
    for k in ["1","2","3"] {
        for arr in dp[i-Int(k)!] { //점화식: dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
            dp[i].append(arr+k) //뒤에 붙이기
            print(dp[i])
        }
    }
}

//i = 4의 경우
//k == "1"
//dp[3]의 원소에 "1"붙여서 dp[4]에 넣기
//dp[4] = "1111", "211", "121", "31"

//k == "2"
//dp[2]의 원소에 "2"붙여서 dp[4]에 넣기
//dp[4] = "1111", "211", "121", "31", "112", "22"

//k == "1"
//dp[1]의 원소에 "3"붙여서 dp[4]에 넣기
//dp[4] = "1111", "211", "121", "31", "112", "22", "13"

let sorted = dp[N].sorted(by: {$0<$1}) //정렬, k번째 경우의 수 찾아야 하므로
if sorted.count < K {
    print(-1)
}else {
    var answer = ""
    sorted[K-1].forEach{answer += String($0)+"+"}
    answer.removeLast()
    print(answer)
}

 

역시 DP가 빠르다.. 빨리 DP 공부를 열심히 해야겠다!