[Softeer] Hanyang Popularity Exceeding Competition (Swift)

https://softeer.ai/practice/9495

Softeer - 현대자동차그룹 SW인재확보플랫폼

DP

N명의 유명인의 인기도(P)와 친화력(C)가 주어질 때, 철민이가 유명인을 만나면 조건에 따라 인기도가 1씩 증가한다.

조건은 |유명인의 인기도 - 철민이의 인기도| <= 유명인의 친화력 이다.

철민이의 인기도가 0부터 시작할 때 어떤 유명인들을 만나야 최대 인기도를 달성할 수 있는지, 그 최댓값을 출력하는 문제

유명인들을 만나는 순서를 변경하는 것은 어렵고, 만날지 안만날지만 선택할 수 있음

 

접근방법

처음에는 유명인들을 순회하면서 만나는 경우와, 안만나는 경우를 모두 구하는 브루트포스 방식으로 DFS 처럼 풀어봤는데,

중간에 시간 초과가 나서, 모두 확인하는 것 보다, 조건을 만족할 때까지는 재귀함수를 호출하지 않는 방식으로도 고쳐봤는데도 시간초과가 났다. 그래서 찾아보니까 DP로 풀어야 된다고 해서 DP로 풀어서 제출하고 통과됐다.

DP 풀이 방식은 N*2 크기의 2차원 배열이고, [i][0] 에는 i를 만나는 경우, i까지의 최대 인기도, [i][1]에는 i를 안만나는 경우, i까지의 최대 인기도를 저장한다.

1) [DP 초기화] 우선 [0][0], [0][1]은 초기화를 해주어야 하는데, 만나면 이득이라면 (조건 만족) [0][0]에는 1, 만나도 똑같다면 (조건 만족 X) [0][0]에는 0을 저장하고, [0][1]은 어차피 만나지 않는 경우이기 때문에, 0으로 남겨둔다.

2) 그럼 이제 1부터 N-1까지 순회하면서 DP 배열을 채운다. 

dp[i][0] 은 조건을 만족하면 i를 만난다는 가정이기 때문에,

a) i-1을 만난 최대 인기도인 dp[i-1][0] 을 현재 민철 인기도라고 했을 때, i를 만나는 경우 = dp[i-1][0]+1 (못 만나면 dp[i-1][0])

b) i-1을 안만난 최대 인기도인 dp[i-1][1] 을 현재 민철 인기도라고 했을 때, i를 만나는 경우 = dp[i-1][1]+1 (못 만나면 dp[i-1][1])

a,b를 비교해서 큰 값을 dp[i][0] 에 저장

 

dp[i][1] 은 i를 안만난다는 조건이기 때문에,

dp[i-1][0] 과 dp[i-1][1]를 비교해서 큰 값을 dp[i][1]에 저장

 

반복문 종료 후 dp[n-1][0], dp[n-1][1] 중 최대값을 출력하면 끝

 

소스코드

import Foundation
// DP 풀이 - 통과
func solution() -> Int {
    var PC:[[Int]] = []

    let N = Int(readLine()!)!
    var dp:[[Int]] = Array(repeating: Array<Int>(repeating: 0, count: 2), count: N)
    
    for _ in 0..<N {
        PC.append(readLine()!.split(separator:" ").map { Int($0)! })
    }

    // DP 초기 설정
    dp[0][0] = abs(PC[0][0] - 0) <= PC[0][1] ? 1 : 0
    
    for i in 1..<N {
        let pi = PC[i][0]
        let ci = PC[i][1]
        // i-1을 만나고 i만나는 경우
        var curX0 = abs(pi - dp[i-1][0]) <= ci ? dp[i-1][0]+1 : dp[i-1][0]
        // i-1을 안만나고 i만나는 경우
        var curX1 = abs(pi - dp[i-1][1]) <= ci ? dp[i-1][1]+1 : dp[i-1][1]
        dp[i][0] = max(curX0, curX1)
        // i를 안만나는 경우
        dp[i][1] = max(dp[i-1][0], dp[i-1][1])
    }
    
    return max(dp[N-1][0], dp[N-1][1])
}

print(solution())

 

시간초과 난 DFS 풀이

var PC:[[Int]] = []
var result:Int = 0

func dfs(_ x:Int, _ i:Int, _ N:Int) {
    if i == N {
        if result < x {
            result = x
        }
        return
    }

    var j = i
    while j < N && abs(PC[j][0]-x) > PC[j][1] {
        j += 1
    }
    if j == N {
        return
    }
    dfs(x+1, j+1, N)
    dfs(x, j+1, N)
}

let N = Int(readLine()!)!
    
for _ in 0..<N {
    PC.append(readLine()!.split(separator:" ").map { Int($0)! })
}

dfs(0,0,N)

print(result)