LIT_15 2022 KAKAO TECH INTERNSHIP

LIT(Learn I Today) 내가 오늘 배운 것들에 대한 정리

프로그래머스 기출문제에 있는 2022 KAKAO TECH INTERNSHIP 문제를 정리해 보고자 한다.

코딩테스트 공부

레벨 : 3
프로그래머스-코딩테스트 연습

느낀점: 진짜 처음보고 뭔지 모르겠었다... 다른 풀이들을 보니 dp를 쓰는데 dp를 쓰는 것 까지는 이해도 되고 나도 생각을 했었다. 근데 float("inf")가 양의 무한대를 뜻한다는 것도 처음 알았고 왜 필요한지를 생각해내기 까지 오래걸렸다. 갈길이 멀다

나의 풀이

"""이풀이는 인터넷에서 본 풀이 인데 
이걸 이해하는 거로도 시간이 좀 걸렸다...."""
def solution(alp, cop, problems):
    max_alp = 0
    max_cop = 0
    time = 0
    # 문제를 전부 풀기위한 알고력과 코딩력 찾기
    for a,b,c,d,e in problems:
        max_alp = max(max_alp,a)
        max_cop = max(max_cop,b)
        #문제를 적어도 한번씩이라도 푸는데 걸리는 시간
        time += e
    alp = min(alp, max_alp)
    cop = min(cop, max_cop)
    INF = float('inf')
    # INF를 사용해야 대수비교가 수월하다.
    dp = [[INF]*(max_cop + 1) for _ in range(max_alp + 1)]
    dp[alp][cop] = 0
    for i in range(alp, max_alp + 1):
        for j in range(cop, max_cop + 1):
            # 목표로 하는 능력치 보다 낮은 능력치는 1씩 더해서 찾음
            if i + 1 <= max_alp:
                dp[i + 1][j] = min (dp[i + 1][j],dp[i][j] + 1)
            if j + 1 <= max_cop:
                dp[i][j + 1] = min (dp[i][j + 1],dp[i][j] + 1)
            # 풀수 있는 문제의 경우 dp판에서 능력치 업데이트
            for alp_req,cop_req,alp_rwd,cop_rwd,cost in problems:
                if i >= alp_req and j >= cop_req:
                    next_alp,next_cop = min(max_alp,i + alp_rwd), min(max_cop,j + cop_rwd)
                    dp[next_alp][next_cop] = min(dp[next_alp][next_cop],dp[i][j] + cost)
    return dp[-1][-1]