🦊 코딩 테스트 공부

1. 문제 링크

코딩 테스트 공부

2. 코드

def solution(alp, cop, problems):
    # dp[151][151] -> alp = 151, cop = 151 이 되는데 걸리는 시간

    problems.sort(key=lambda x : -x[0])
    req_alp = max(problems[0][0], alp)
    problems.sort(key=lambda x : -x[1])
    req_cop = max(problems[0][1], cop)

    # 무한대로 초기화
    INF = 200*200
    dp = []
    for i in range(151):
        dp.append([INF] * (151))

    # 현재 레벨을 0으로 초기화
    dp[alp][cop] = 0

    for i in range(alp, req_alp + 1):
        for j in range(cop, req_cop + 1):
            # 값이 존재하면 계산
            if dp[i][j] != INF:
                # 알고리즘 공부
                next_i = min(req_alp, i + 1)
                dp[next_i][j] = min(dp[i][j] + 1, dp[next_i][j])
                # 코딩력 공부
                next_j = min(req_cop, j + 1)
                dp[i][next_j] = min(dp[i][j] + 1, dp[i][next_j])
                # 문제 풀기
                for problem in problems:
                    alp_req, cop_req, alp_rwd, cop_rwd, cost = problem
                    
                    # 문제를 풀수 있는 레벨이면
                    if i >= alp_req and j >= cop_req:
                        # 범위를 초과하지 않는 선에서 레벨 증가
                        next_alp = min(req_alp, i + alp_rwd)
                        next_cop = min(req_cop, j + cop_rwd)
                        dp[next_alp][next_cop] = min(dp[i][j] + cost, dp[next_alp][next_cop])

    return dp[req_alp][req_cop]

• 정확성

  채점을 시작합니다. 정확성 테스트 테스트 1 〉 통과 (0.37ms, 10.5MB) 테스트 2 〉 통과 (0.68ms, 10.3MB) 테스트 3 〉 통과 (0.36ms, 10.3MB) 테스트 4 〉 통과 (0.26ms, 10.3MB) 테스트 5 〉 통과 (0.32ms, 10.4MB) 테스트 6 〉 통과 (0.38ms, 10.3MB) 테스트 7 〉 통과 (0.24ms, 10.3MB) 테스트 8 〉 통과 (0.20ms, 10.5MB) 테스트 9 〉 통과 (0.24ms, 10.3MB) 테스트 10 〉 통과 (0.20ms, 10.4MB) 효율성 테스트 테스트 1 〉 통과 (20.62ms, 10.3MB) 테스트 2 〉 통과 (27.08ms, 10.4MB) 테스트 3 〉 통과 (3.81ms, 10.3MB) 테스트 4 〉 통과 (20.10ms, 10.4MB) 테스트 5 〉 통과 (135.45ms, 10.5MB) 테스트 6 〉 통과 (33.53ms, 10.4MB) 테스트 7 〉 통과 (165.69ms, 10.3MB) 테스트 8 〉 통과 (138.94ms, 10.3MB) 테스트 9 〉 통과 (331.87ms, 10.4MB) 테스트 10 〉 통과 (4.76ms, 10.4MB) 채점 결과 정확성: 50.0 효율성: 50.0 합계: 100.0 / 100.0

3. 해설

• 해설

  dp[i][j] ⇒ alp = i, cop = j 가 되는데 걸리는 시간

  초기값 부터 배열을 순회하면 값이 INF 가 아닐 경우 모든 경우의수에 대한 계산 수행

  범위를 벗어나지 않도록 값을 조정할 필요가 있음