[백준/Swift] 14501번 퇴사(백트래킹)

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

14501번: 퇴사

 

N일동안 최대한 많은 상담을 하고, 최대 수익을 얻어라.

이 문제는 N이 15보다 작기 때문에, 완전탐색으로 해도 충분할 거라고 생각했다. 게다가 시간제한이 2초!

 

DFS를 사용해서 시작날짜로부터 깊게 들어가도록 했다.

튜플을 사용해서 (기간, 금액) 배열을 만들고, 1일~N일을 시작날짜로 잡고 DFS를 돌렸다.

여기서 N일도 가능한 것은 1일 상담이라면 N일도 가능하기 때문. 모든 날짜가 가능한것은 아닌데, 만약 해당 날짜에 시작한 상담이 퇴사날을 넘어서게 된다면 이 상담은 하지 않아야 한다. 그러므로 이 경우는 continue로 빠져나갔다.

 

DFS에서 빠져나갈 조건은 해당 날(x)이 마지막 날(n)인 경우 또는 해당 날에서 시작한 상담이 마지막 날을 넘어서는 경우

이 경우 answer를 업데이트해주고 리턴한다.

 

x에서 시작해서 다음 상담 날은 x날에 진행한 상담이 끝난 다음날부터다.

여기서도 조건이 하나 있는데, 바로 이 상담날의 상담이 마지막 날을 넘어서는지 체크해줘야 한다는 것이다.

넘어서지 않는다면 DFS로 그 다음 상담날로 넘어간다.

 

만약 다음 상담날이 없다면 answer를 업데이트하고 리턴해서 종료한다.

 

import Foundation

let n = Int(readLine()!)!
var array = [(0,0)] //기간, 금액
var answer = 0

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

func DFS(_ x: Int, _ sum: Int){
    if x == n || x + array[x].0 > n {
        answer = max(answer, sum)
        return
    }
    
    for i in array[x].0 + x...n { //다음 상담 날(인덱스)
        if i + array[i].0 - 1 > n {
            continue
        }
        DFS(i, sum + array[i].1)
    }
    
    answer = max(answer, sum)
    return
}

for d in 1...n { //시작하는 날짜
    if d + array[d].0 - 1 > n { continue }
    DFS(d, array[d].1)
}

print(answer)

 

알고리즘 분류를 보니 DP로도 풀수 있는 것 같다. 다음에는 이 걸로 다시 풀어봐야겠다!