🐹 코딩 테스트 공부

1. 문제 링크

코딩 테스트 공부

2. 코드

INF = int(1e9)

def solution(alp, cop, problems):
    problems.sort(key=lambda x : -x[0])
    min_alp = max(problems[0][0], alp)
    problems.sort(key=lambda x : -x[1])
    min_cop = max(problems[0][1], cop)
    
    dp = [[INF] * 151 for _ in range(151)]
    dp[alp][cop] = 0
    
    # 공부 이전에 이미 모든 문제 풀 수 있을 때
    if alp >= min_alp and cop >= min_cop:
        return 0
    
    def can_solve(now_alp, now_cop, p):
        a, c, ua, uc, cost = p
        return now_alp >= a and now_cop >= c
    
    def possible_alp_index(idx):
        if idx > min_alp:
            return min_alp
        else:
            return idx
        
    def possible_cop_index(idx):
        if idx > min_cop:
            return min_cop
        else:
            return idx
    
    for i in range(alp, min_alp + 1):
        for j in range(cop, min_cop + 1):
            # 알고리즘을 공부하여 알고력 1 올리기
            alp_idx = possible_alp_index(i+1)
            dp[alp_idx][j] = min(dp[alp_idx][j], dp[i][j] + 1)
            # 코딩을 공부하여 코딩력 1 올리기
            cop_idx = possible_cop_index(j+1)
            dp[i][cop_idx] = min(dp[i][cop_idx], dp[i][j] + 1)
            # 문제를 풀어 알고력, 코딩력 올리기
            for p in problems:
                a, c, ua, uc, cost = p
                if can_solve(i, j, p):
                    alp_idx, cop_idx = possible_alp_index(i+ua), possible_cop_index(j+uc)
                    dp[alp_idx][cop_idx] = min(dp[alp_idx][cop_idx], dp[i][j] + cost)
    
    return dp[min_alp][min_cop]

• 정확성

테스트 1 〉	통과 (0.62ms, 10.4MB)
테스트 2 〉	통과 (0.66ms, 10.4MB)
테스트 3 〉	통과 (0.36ms, 10.4MB)
테스트 4 〉	통과 (0.19ms, 10.4MB)
테스트 5 〉	통과 (0.34ms, 10.4MB)
테스트 6 〉	통과 (0.43ms, 10.4MB)
테스트 7 〉	통과 (0.20ms, 10.3MB)
테스트 8 〉	통과 (0.20ms, 10.5MB)
테스트 9 〉	통과 (0.28ms, 10.4MB)
테스트 10 〉	통과 (0.19ms, 10.5MB)

• 효율성

테스트 1 〉	통과 (34.96ms, 10.4MB)
테스트 2 〉	통과 (30.26ms, 10.5MB)
테스트 3 〉	통과 (4.83ms, 10.5MB)
테스트 4 〉	통과 (23.22ms, 10.2MB)
테스트 5 〉	통과 (171.49ms, 10.4MB)
테스트 6 〉	통과 (40.59ms, 10.5MB)
테스트 7 〉	통과 (210.64ms, 10.4MB)
테스트 8 〉	통과 (162.95ms, 10.4MB)
테스트 9 〉	통과 (384.07ms, 10.3MB)
테스트 10 〉	통과 (5.62ms, 10.3MB)

3. 해설

문제를 모두 풀기 위해서는 문제들 중 필요한 최대 알고력과 최대 코딩력을 만족해야 한다.

각 알고력과 코딩력에 도달했을 때의 최소 시간을 dp에 저장한다.

⇒ ‘dp[알고력][코딩력] = 걸리는 최소 시간’

처음 알고력, 코딩력일 때는 0으로 초기화 해주고 나머지 dp 값은 무한대로 설정해준다.

3가지 경우로 알고력, 코딩력을 높일 수 있다.

1. 알고리즘 공부를 하여 알고력 1 올리기

   → dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)

2. 코딩 공부를 하여 코딩력 1 올리기

   → dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)

3. 문제를 풀어 알고력, 코딩력 올리기

   문제를 풀었을 때 오르는 알고력 : ua

   문제를 풀었을 때 오르는 코딩력 : uc

   문제를 풀었을 때 걸리는 시간 : cost

   → dp[i+ua][j+uc] = min(dp[i+ua][j+uc], dp[i][j] + cost)

각 결과를 dp에 저장하고 이때 모든 문제를 풀기 위한 최소 시간은 dp[목표 알고력][목표 코딩력]이다.

⭐ 이때 (처음 알고력, 처음 코딩력)이 (목표 알고력, 목표 코딩력)보다 큰 경우에 더 큰 값을 목표 값으로 변형하고 dp값을 초기화해야한다.

⭐ dp에 알고력, 코딩력의 인덱스로 접근할 때 목표를 넘어가거나 정해진 크기보다 더 큰 값으로 접근할 경우 런타임 에러가 발생할 수 있다. 따라서 (목표 알고력, 목표 코딩력)보다 큰 인덱스로 접근할 경우를 막기 위해 인덱스가 더 클 경우 목표 알고력, 목표 코딩력으로 바꾸어준 후 계산한다.