[2023 KAKAO TECH INTERNSHIP 코딩 테스트 공부] (Python)

문제-문제링크

프로그래머스

 

유형 

• dp 

문제풀이 

• '모든 문제를 1번 이상씩 풀 필요는 없다' 라는 조건을 보고 dp로 먼저 접근했음 
• dp 테이블 -> row: 알고력, col: 코딩력을 축으로 하는 2차원 배열,
  dp[i][j] = (알고력 i, 코딩력 j를 얻기 위한 최소 비용)
• 로직구성 
  
  1. 문제들의 최대 알고력, 최대 코딩력을 구한다. 
     이때, 주어진 초기 alp, cop가 문제들의 알고력, 코딩력보다 클 수 있으므로
     max_alp= max(문제의 최대 알고력, 초기 alp)
     max_cop = max(문제의 최대 코딩력, 초기 cop)  해주어야 dp 리스트 out of range 에러가 발생하지 않는다 
  2. max_alp, max_cop 크기의 dp테이블 선언, 초기값은 INF로 세팅 
  3. (alp, cop) 상태부터 시작해서 모든 종류의 문제를 한번씩 풀어보고 얻을 수 있는 알고력, 코딩력 상태의 최소비용을 갱신해준다.
     dp[nxt_alp][nxt_cop] = min(dp[nxt_alp][nxt_cop], dp[alp][cop]+문제 푸는 비용 )
  4. 이때, nxt_alp, nxt_cop가 max_cop, max_alp를 넘어가는 경우 nxt_alp = min(nxt_alp, max_alp), nxt_cop = min(nxt_cop, max_cop) 로 제한한다. ** 이거 생각 못하고 한참 디버깅 했음**
     (범위 넘어가면 그냥 pass 했는데 범위 벗어나도 문제를 모두 풀 수 있는 능력치를 갖춘 상태이므로 해당 비용이 최소 비용이 되는지 확인해야함)

코드 

def solution(alp, cop, problems):
    answer = 0
    
    max_alp, max_cop = 0,0 
    for prob in problems:
        if prob[0] > max_alp:
            max_alp = prob[0]
        if prob[1] > max_cop:
            max_cop = prob[1]
    
    if alp>= max_alp and cop >= max_cop:
        return 0 
    max_alp = max(max_alp, alp)
    max_cop = max(max_cop, cop)
    dp = [[int(1e9) for _ in range(max_cop+1)] for _ in range(max_alp+1)]
    dp[alp][cop] = 0 
    
    problems += [[0, 0, 1, 0, 1], [0, 0, 0, 1, 1]]
    for i in range(alp, max_alp+1):
        for j in range(cop, max_cop+1):
            if (i, j) == (max_alp, max_cop):
                continue 
            #각 상태에서 모든 문제 한번씩 풀어보고 도달 가능한 능력치의 최소비용 갱신 
            for prob in problems:
                if i>= prob[0] and j >= prob[1]: #풀 수 있음 
                    nxt_alp, nxt_cop = i + prob[2], j + prob[3] 
                    nxt_alp, nxt_cop = min(nxt_alp, max_alp), min(nxt_cop, max_cop)
                    
                    # if nxt_alp > max_alp or nxt_cop > max_cop: ##디버깅, 오답 
                        # continue 
                    dp[nxt_alp][nxt_cop] = min(dp[nxt_alp][nxt_cop], dp[i][j] + prob[4])
                    
    
    answer = dp[max_alp][max_cop]    
    
    
    return answer