Created
August 29, 2022 15:39
-
-
Save daejinseok/cdbb995a80a6f47460308a876a230384 to your computer and use it in GitHub Desktop.
코딩테스트 연습 2022 KAKAO TECH INTERNSHIP 코딩 테스트 공부
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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