Skip to content

Instantly share code, notes, and snippets.

@daejinseok
Created August 29, 2022 15:39
Show Gist options
  • Save daejinseok/cdbb995a80a6f47460308a876a230384 to your computer and use it in GitHub Desktop.
Save daejinseok/cdbb995a80a6f47460308a876a230384 to your computer and use it in GitHub Desktop.
코딩테스트 연습 2022 KAKAO TECH INTERNSHIP 코딩 테스트 공부
# https://school.programmers.co.kr/learn/courses/30/lessons/118668#qna
import math
def solution(alp, cop, problems):
# 필요 능력 구하기
alp_max = 0
cop_max = 0
for alp_req, cop_req, _, _, _ in problems:
alp_max = max(alp_max, alp_req)
cop_max = max(cop_max, cop_req)
# 기본 학습능력 추가
problems.append([0, 0, 1, 0, 1])
problems.append([0, 0, 0, 1, 1])
# 자주 사용하는 값은 미리 계산해 두자
alp_max_1 = alp_max + 1
cop_max_1 = cop_max + 1
INF = math.inf
# 초기능력이 이미 능가한 경우가 있다고 함
alp = min(alp_max, alp)
cop = min(cop_max, cop)
# 초기배열
dp = [[INF]*cop_max_1 for _ in range(alp_max_1)]
dp[alp][cop] = 0
def walk(dp, alp, cop, p):
alp_req, cop_req, alp_rwd, cop_rwd, cost = p
if alp < alp_req or cop < cop_req:
return
alp_jump = min(alp_max, alp + alp_rwd)
cop_jump = min(cop_max, cop + cop_rwd)
dp[alp_jump][cop_jump] = min(
dp[alp_jump][cop_jump], dp[alp][cop] + cost)
# gogo
for a in range(alp, alp_max_1):
for c in range(cop, cop_max_1):
for p in problems:
walk(dp, a, c, p)
return dp[alp_max][cop_max]
print(solution(10, 10, [[10, 15, 2, 1, 2], [20, 20, 3, 3, 4]]))
assert solution(10, 10, [[10, 15, 2, 1, 2], [20, 20, 3, 3, 4]]) == 15
assert solution(0, 0, [[0, 0, 2, 1, 2], [4, 5, 3, 1, 2], [
4, 11, 4, 0, 2], [10, 4, 0, 4, 2]]) == 13
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment