코딩테스트 공부
🍎 지문 해석
- 알고력과 코딩력을 모든 문제를 풀 수 있도록 키우자!
- 아래 두가지 방법으로 알고력과 코딩력을 키울 수 있다.
- 트레이닝 -> 1시간을 소비해 알고력 또는 코딩력 중 하나를 1 높일 수 있다.
- 문제 풀기 -> 알고력, 코딩력이 문제를 풀 수 있는 레벨이 된다면, 문제를 풀어 알고력과 코딩력을 늘릴수 있다.
- alp는 현재 알고력
- cop는 현재 코딩력
- problems는
- (문제의 풀기위한 알고력,
- 문제의 풀기위한 코딩력,
- 문제를 풀었을때 보상 알고력,
- 문제를 풀었을때 보상 코딩력,
- 문제를 푸는데 걸리는 시간)
- 순으로 주어진다.
🍎 문제 접근
- 문제를 다 푸는데까지 걸리는 최단 시간을 구하는것이 이 문제의 답이다.
- 매개변수에 주어지는 초기 알고력 or 코딩력이 모든 문제를 풀 수 있는 최대 알고력 or 코딩력을 넘어설 수 있다.
- 이때는 문제들을 순회하면서 모든 문제를 풀기 위해 필요한 가장 큰 알고력 or 코딩력으로 둔다
- 이렇게 해야하는 이유는..
- 필요 이상의 연산을 하지 않도록 하기 위해서다.
- 예를들어 모든 문제를 풀기 위해서는 알고력 20, 코딩력 20이 필요하다고 가정해보자
- 하지만 처음 주어지는 알고력이 25, 코딩력이 10이라면 20까지만 계산해도 될것을 불필요하게 25까지 계산하게 되는것이다.
- 문제를 풀기위해서는 모든 문제를 풀기위해 필요한 최소의 알고력이다.
- 즉, 그 이상의 알고력은 필요 없다는 의미다.
- 최단 시간을 저장하는 dp배열의 사이즈를 줄일 수 있다.
- 두가지 이유 모두 퍼포먼스를 드라마틱하게 올려주지 않지만, 필요하지 않은 코드다.
🍎 문제 풀이 및 전체 코드
import Foundation
func solution(_ alp: Int, _ cop: Int, _ problems: [[Int]]) -> Int {
// alp = 현재 알고리즘 능력
// cop = 현재 코딩 능력
// max_alp_req는 최대 알고리즘 능력
// max_cop_req는 최대 코딩 능력
// 즉, max에 도달하면 문제를 다 풀 수 있기 때문에 더 이상 진행 시킬 필요없다.
var max_alp_req = 0
var max_cop_req = 0
for problem in problems {
max_alp_req = max(max_alp_req, problem[0])
max_cop_req = max(max_cop_req, problem[1])
}
//MARK: 초기 주어지는 알고력 or 코딩력이 max 보다 더 클 수 있다.
var newALP = min(max_alp_req, alp)
var newCOP = min(max_cop_req, cop)
//MARK: 범위는 최대 알고력 * 최대 코딩력으로 두었다. 아래서 계산할 때 이 부분을 넘어가지 않도록 막을것.
var dp = [[Int]](repeating: [Int](repeating: Int.max, count: max_cop_req + 1), count: max_alp_req + 1)
dp[newALP][newCOP] = 0
for i in newALP...max_alp_req {
for j in newCOP...max_cop_req {
if i + 1 <= max_alp_req { // 알고력 늘려주기
// 가려는 곳(dp[i+1][j]에 이미 있던 값 vs 이전값 + 1 한것 중 더 작은것으로 갱신 해준다.
dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
}
if j + 1 <= max_cop_req { // 코딩력 늘려주기
// 가려는 곳(dp[i][j+1])에 이미 있던 값 vs 이전값 + 1 한것 중 더 작은것으로 갱신 해준다.
dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
}
for problem in problems {
let alp_req = problem[0]
let cop_req = problem[1]
let alp_rwd = problem[2]
let cop_rwd = problem[3]
let cost = problem[4]
//MARK: 현재 i,j가 문제를 풀 수 있는 능력이 된다면(equal or above),
if i >= alp_req && j >= cop_req {
// 풀었을때 어느 위치로 가는지 찾는다. (이때 i + alp_rwd가 max_alp_req를 넘을 수 있으므로 둘 중 더 작은것을 넣어준다.)
let safeALP = min(i + alp_rwd, max_alp_req)
let safeCOP = min(j + cop_rwd, max_cop_req)
// 해당 위치에 도달 했을때 최소 비용을 구한다.
dp[safeALP][safeCOP] = min(dp[safeALP][safeCOP], dp[i][j] + cost)
}
}
}
}
return dp[max_alp_req][max_cop_req]
}
🍎 문제를 풀고 생각한 점
- BFS로 풀려했다가 방문처리가 없다면 무한정 탐색할 것 같아 감 못잡다가 다른분들이 푼것을 조금 더 쉽게 만들었다.
- 문제를 풀 때 브루트포스를 가장 먼저 생각하는것처럼 최단거리, 최소비용을 구하는 것이라면 DP, 플로이드-와샬(N^3), 다익스트라(ElogV), BFS(가중치가 동일할 때) 순서로 생각하자!
- 이 문제는 다익스트라로 풀어도 될거 같은데, 시간 복잡도만 계산해보자!
- N^2log(N^2) -> N^2log(N) -> 20^2log(20) = 400
