[프로그래머스] 코딩 테스트 공부

2022 KAKAP TECH INTERNSHIP 

코딩 테스트 공부

DP

 

---

※ 카카오 공식 해설

https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/

2022 테크 여름인턴십 코딩테스트 해설

 

 

[문제]

 

문제가 생각보다 어려워서 카카오 해설을 참고했다.

 

여기서 짚고 넘어갈 부분은 (초기 알고력, 초기 코딩력) 상태에서 시작해 (목표 알고력, 목표 코딩력) 상태에 도달하는 최단 시간을 구하는 문제라는 것

 

'알고력'과 '코딩력'이라는 두가지 값이 필요하므로 DP배열을 2차원으로 생성해줘야한다.

 

• dp[i][j] : (알고력 i, 코딩력 j) 상태에 도달하는 데 필요한 최단 시간

---

[과정]

 

DP 배열을 정의하면 문제에서 요구하는 답은 dp[목표 알고력][목표 코딩력]

dp[초기 알고력][초기 코딩력] = 0으로 기저 사례를 잡고 나머지 DP 배열의 값은 무한값으로 초기화한 후 for문에서 DP 배열을 업데이트 하는 방식으로 풀면 된다.

 

 

• problems에서 주어진 값을 이용해 max_alp, max_cop 구하기
• 2차원 dp배열 초기화
  • dp[alp][cop] = 0      # 알고력 i, 코딩력 j을 도달 할 수 있는 최단시간
• alp,cop 예외처리
  • 시작 알고력이 max알고력보다 크거나, 시작 코딩력이 max코딩력보다 클때 dp[alp][cop]=0에서 indexError가 발생하기 때문에 max_alp, max_cop값이 주어진 값중 최댓값을 넘지 않도록 함
• 2중 for문 수행      # 모든 problem에 대해서 반복문 수행하기
  • 알고리즘을 공부하여 알고력을 1 높이는 경우:
    dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1)
  • 코딩을 공부하여 코딩력을 1 높이는 경우:
    dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1)
  • 문제 하나를 선택하여 알고력과 코딩력을 높이는 경우:
    dp[i+alp_rwd][j+cop_rwd] = min(dp[i+alp_rwd][j+cop_rwd], dp[i][j]+cost) (단, i >= alp_req이고 j >= cop_req)
• dp[max_alp][max_cop] 출력

 

---

[소스코드]

 

def solution(alp, cop, problems):
    INF = 1e9
    max_alp, max_cop = [0, 0]  # 목표값
    
    for problem in problems:
        max_alp = max(max_alp, problem[0])
        max_cop = max(max_cop, problem[1])
    
    dp = [[INF] * (max_cop+1) for _ in range(max_alp+1)]  # 무한값으로 2차원 dp배열 초기화 -> 최소횟수를 갱신해야 하기 때문
   
    # 초기의 알고력(코딩력) 자체가 alp_max(cop_max)보다 높은 경우에 대한 예외처리
    # 이유 : 시작 알고력이 max알고력보다 크거나, 시작 코딩력이 max코딩력보다 클때 dp[alp][cop]=0에서 런타임 에러가 발생
    alp = min(alp, max_alp)  
    cop = min(cop, max_cop)
    
    dp[alp][cop] = 0  # dp[i][j]의 의미 : 알고력 i, 코딩력 j을 도달 할 수 있는 최단시간 (시작점)
    
    for i in range(alp, max_alp+1):
        for j in range(cop, max_cop+1):
            
            # 알고리즘을 공부하여 알고력을 1 높이는 경우
            if i < max_alp:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
                
            # 코딩을 공부하여 코딩력을 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 i >= alp_req and j >= cop_req:   # 문제를 풀 수 있는 경우 
                    nxt_alp = min(i+alp_rwd, max_alp)  # 둘중 하나라도 목표값을 넘어가면 안됨
                    nxt_cop = min(j+cop_rwd, max_cop)
                    dp[nxt_alp][nxt_cop] = min(dp[nxt_alp][nxt_cop], dp[i][j] + cost)
             
    return dp[max_alp][max_cop]

 

---

[통과]

 

---

 

5/12 스터디 과제 2