99클럽 코테 스터디 42일차 TIL, 프로그래머스 / 코딩테스트공부

🔑 오늘의 학습 키워드 : DP

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/118668

 

def solution(alp, cop, problems):
    max_alp, max_cop = 0,0
    for p in problems:
        max_alp = max(max_alp,p[0])
        max_cop = max(max_cop,p[1])
        
    # 현재 alp와 cop가 목표보다 높을 경우를 대비
    alp = min(alp, max_alp)
    cop = min(cop, max_cop)
    
    dp = [[1e9] * (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):
            # 공부해서 능력을 올리는 경우
            if i < max_alp:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
            if j < max_cop:
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
            
            # 문제를 풀어서 능력을 올리는 경우
            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
                if alp_req <= i and cop_req <= j:
                    new_alp = min(max_alp, i + alp_rwd)
                    new_cop = min(max_cop, j + cop_rwd)
                    dp[new_alp][new_cop] = min(dp[new_alp][new_cop], dp[i][j] + cost)
                
                
    return dp[max_alp][max_cop]

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

그리디? DP? 알고리즘이 어떤 것인지를 우선 판단을 해야했는데

 

문제 내용 중에서 이런 문장이 있었다.

문제를 하나 푸는 데는 문제가 요구하는 시간이 필요하며 같은 문제를 여러 번 푸는 것이 가능합니다.

 

이거 보고 냅색 알고리즘이 떠올랐는데 냅색 알고리즘에 2개 종류 즉

 

중복이 가능한 경우와 가능하지 않는 경우에 대해 떠올렸고 DP를 활용해서 풀어봤다.

⏰ 예상 시간 복잡도 O(150 * 150 * 100)

제한 사항

초기의 알고력을 나타내는 alp와 초기의 코딩력을 나타내는 cop가 입력으로 주어집니다.
0 ≤ alp,cop ≤ 150
1 ≤ problems의 길이 ≤ 100
problems의 원소는 [alp_req, cop_req, alp_rwd, cop_rwd, cost]의 형태로 이루어져 있습니다.
alp_req는 문제를 푸는데 필요한 알고력입니다.
0 ≤ alp_req ≤ 150
cop_req는 문제를 푸는데 필요한 코딩력입니다.
0 ≤ cop_req ≤ 150
alp_rwd는 문제를 풀었을 때 증가하는 알고력입니다.
0 ≤ alp_rwd ≤ 30
cop_rwd는 문제를 풀었을 때 증가하는 코딩력입니다.
0 ≤ cop_rwd ≤ 30
cost는 문제를 푸는데 드는 시간입니다.
1 ≤ cost ≤ 100
정확성 테스트 케이스 제한사항

0 ≤ alp,cop ≤ 20
1 ≤ problems의 길이 ≤ 6
0 ≤ alp_req,cop_req ≤ 20
0 ≤ alp_rwd,cop_rwd ≤ 5
1 ≤ cost ≤ 10

😎 알고리즘 개요

 

1. 초기 테이블 세팅

    max_alp, max_cop = 0,0
    for p in problems:
        max_alp = max(max_alp,p[0])
        max_cop = max(max_cop,p[1])
        
    # 현재 alp와 cop가 목표보다 높을 경우를 대비
    alp = min(alp, max_alp)
    cop = min(cop, max_cop)
    
    dp = [[1e9] * (max_cop+1) for _ in range (max_alp+1)]
    dp[alp][cop] = 0

 

2. dp 테이블 채우기

    for i in range (alp,max_alp+1):
        for j in range (cop,max_cop+1):
            # 공부해서 능력을 올리는 경우
            if i < max_alp:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
            if j < max_cop:
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
            
            # 문제를 풀어서 능력을 올리는 경우
            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
                if alp_req <= i and cop_req <= j:
                    new_alp = min(max_alp, i + alp_rwd)
                    new_cop = min(max_cop, j + cop_rwd)
                    dp[new_alp][new_cop] = min(dp[new_alp][new_cop], dp[i][j] + cost)

 

 

✅ 오늘의 회고

- 항해 99 마지막 문제까지 잘 완료했다

- 그동안 고생하셨습니다

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL