2022 KAKAO TECH INTERNSHIP - 118668. 코딩 테스트 공부
[Lv. 3]
https://school.programmers.co.kr/learn/courses/30/lessons/118668
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
보자마자.. DP로 접근해야 될 것 같은 문제라고 생각했다.
[백준] 2342. Dance Dance Revolution - 파이썬 과 비슷한 느낌으로, Bottom-Up으로 풀면 된다.
dp[alp][cop] => 특정 alp, cop를 달성하기 위한 최소 시간(cost)
def solution(alp, cop, problems): INF = 10**9 max_alp, max_cop = 0, 0 for p in problems: max_alp = max(max_alp, p[0]) max_cop = max(max_cop, p[1]) # 런타임 에러 해결 if alp > max_alp: alp = max_alp if cop > max_cop: cop = max_cop dp = [[INF]*(max_cop+1) for _ in range(max_alp+1)] dp[alp][cop] = 0 # 현재 alp부터 필요 alp까지, 현재 cop부터 필요 cop까지의 dp 배열을 memoization을 이용해 채워 나감. 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 p in problems: if i >= p[0] and j >= p[1]: alp_n = i+p[2] cop_n = j+p[3] # 필요 범위(배열 범위 밖)으로 넘어가면, max값으로 줄여줌. if alp_n > max_alp: alp_n = max_alp if cop_n > max_cop: cop_n = max_cop # 최솟값 최신화! dp[alp_n][cop_n] = min(dp[alp_n][cop_n], dp[i][j]+p[4]) return dp[max_alp][max_cop]