문제 보기 · Level 3 · 2022 KAKAO TECH INTERNSHIP · 정답률 28% · 푼 사람 4,102명 (2026-09-30 기준)1
문제
지금 알고력 alp, 코딩력 cop이 있다. 문제마다 [필요 알고력, 필요 코딩력, 오르는 알고력, 오르는 코딩력, 걸리는 시간]이 주어진다. 할 수 있는 일은 세 가지다.
- 시간 1을 써서 알고력을 1 올린다.
- 시간 1을 써서 코딩력을 1 올린다.
- 지금 풀 수 있는 문제 하나를 풀어, 그 문제의 시간을 쓰고 보상만큼 두 힘을 올린다. 같은 문제를 여러 번 풀어도 된다.
모든 문제를 풀 수 있는 알고력과 코딩력을 갖추는 최소 시간을 돌려준다(문제를 실제로 다 풀 필요는 없다).
- 0 ≤ alp, cop ≤ 150, 문제 1 ~ 100개
- 필요한 힘 0 ~ 150, 보상 0 ~ 30, 시간 1 ~ 100
풀이
막히면 한 단계씩 펼친다.
필요한 개념
동적 계획법: 상태를 (알고력, 코딩력)으로 잡고, 칸마다 “여기까지 오는 최소 시간”을 적는다. 힘은 줄지 않으니 작은 칸부터 채우면 된다.
1단계 · 작은 예로 손으로 풀기
예시 1: 알고력 10, 코딩력 10. 문제 1은 [10, 15, 2, 1, 2], 문제 2는 [20, 20, 3, 3, 4]다. 목표는 두 문제 모두 풀 수 있는 (20, 20)이다.
- 공부만 하면 알고력 10 + 코딩력 10 = 20의 시간이다.
- 코딩력을 5 올려(시간 5) (10, 15)가 되면 문제 1을 풀 수 있다. 문제 1을 다섯 번 풀면(시간 10) (20, 20)이다. 모두 15다.
답은 15다. 문제를 푸는 편이 시간당 더 많이 오르면 공부보다 낫다. 이런 선택이 이어지고 같은 (알고력, 코딩력)에 여러 길로 도착하니 DP가 맞다.
2단계 · 가장 단순한 방법과 그 속도
매 순간 할 일(공부 두 가지 + 문제 최대 100개)을 모두 이어 붙여 보면 가짓수가 폭발한다. 하지만 상태는 (알고력, 코딩력) 한 쌍뿐이다. 이 쌍이 몇 개인지만 줄이면 된다.
3단계 · 핵심 아이디어
- 목표를 넘는 힘은 목표로 친다: 목표 A = 필요 알고력의 최댓값, C = 필요 코딩력의 최댓값이다. 알고력이 A를 넘어도 할 수 있는 일은 A일 때와 같다. 그래서 A를 넘는 값은 A로, C를 넘는 값은 C로 자른다. 그러면 상태는 많아야 151 × 151개다. A 이상인 알고력을 모두 한 동치류로 묶고 A를 대표로 쓰는 셈이다(코딩력도 C로 같다).
- 상태와 점화식: dp[a][c] = (a, c)에 도착하는 최소 시간. (a, c)에서 할 수 있는 일마다 다음 칸의 값을 줄인다.
- 공부: dp[a + 1][c], dp[a][c + 1]을 dp[a][c] + 1로
- 풀 수 있는 문제: dp[min(A, a + 보상)][min(C, c + 보상)]을 dp[a][c] + 시간으로
- 시작값: 처음 힘도 목표로 자른 칸이 0, 나머지는 무한대다.
- 계산 순서: 모든 일이 힘을 늘리기만 하니, a를 작은 쪽부터, 그 안에서 c를 작은 쪽부터 채우면 읽는 칸이 늘 먼저 채워져 있다. 자른 뒤 제자리로 돌아오는 경우(보상이 0이거나 이미 목표)는 건너뛴다. 이 순서는 칸 사이 의존 관계를 한 줄로 세운 위상 정렬의 하나다.
- 답: dp[A][C].
4단계 · 코드 흐름
- A, C를 구하고 처음 힘을 A, C로 자른다.
- (A + 1)×(C + 1) 표를 무한대로, 시작 칸을 0으로 채운다.
- a, c를 작은 쪽부터 돌며, 도착한 칸에서 공부 두 가지와 풀 수 있는 문제로 다음 칸을 줄인다.
- dp[A][C]를 돌려준다.
5단계 · 파이썬 코드
def solution(alp, cop, problems):
A = max(p[0] for p in problems) # 목표 알고력
C = max(p[1] for p in problems) # 목표 코딩력
alp, cop = min(alp, A), min(cop, C) # 목표를 넘는 힘은 목표로 친다
INF = float("inf")
dp = [[INF] * (C + 1) for _ in range(A + 1)]
dp[alp][cop] = 0
for a in range(alp, A + 1):
for c in range(cop, C + 1):
t = dp[a][c]
if t == INF:
continue
if a < A and t + 1 < dp[a + 1][c]: # 알고리즘 공부
dp[a + 1][c] = t + 1
if c < C and t + 1 < dp[a][c + 1]: # 코딩 공부
dp[a][c + 1] = t + 1
for ra, rc, wa, wc, cost in problems:
if a >= ra and c >= rc: # 풀 수 있는 문제
na, nc = min(A, a + wa), min(C, c + wc)
if (na, nc) != (a, c) and t + cost < dp[na][nc]:
dp[na][nc] = t + cost
return dp[A][C]
- 이 코드는 “지금 칸에서 다음 칸으로 밀어 주는” 방식이다. 개념 문서의 동전 문제처럼 “앞 칸에서 당겨 오는” 방식과 결과가 같다. 다음 칸이 여러 곳이라 밀어 주기가 편하다.
- 처음부터 힘이 목표 이상이면 시작 칸이 곧 (A, C)라 0을 돌려준다.
6단계 · 실행 추적
예시 1에서 코딩력을 5 올린 뒤 문제 1만 되풀이하는 길의 칸 값이다.
| 칸 (알고력, 코딩력) | dp | 온 방법 |
|---|---|---|
| (10, 10) | 0 | 시작 |
| (10, 15) | 5 | 코딩 공부 5번 |
| (12, 16) | 7 | 문제 1 |
| (14, 17) | 9 | 문제 1 |
| (16, 18) | 11 | 문제 1 |
| (18, 19) | 13 | 문제 1 |
| (20, 20) | 15 | 문제 1 |
공부만으로 (20, 10)에 가면 10, 거기서 코딩력을 10 더 올리면 20이다. dp[20][20] = 15가 답이다.
7단계 · 복잡도와 흔한 실수
상태 (A + 1)(C + 1) ≤ 151² ≈ 2.3만 개, 칸마다 문제 100개를 보니 약 230만 번이다. 재 보니 0.1초 안팎이었다.
- 목표를 넘는 힘을 자르지 않아 칸 번호가 표 밖으로 나간다. 표를 크게 잡아도 상태가 불필요하게 늘어난다.
- 목표를 넘어서는 쪽을 버리는 대신 “넘으면 그 문제를 풀지 않는다”로 처리해 답을 놓친다. 알고력이 넘쳐도 코딩력을 위해 같은 문제를 계속 풀어야 할 때가 있다.
- 처음 힘이 이미 목표 이상인 경우를 빼먹어 표 밖을 읽는다.
-
프로그래머스 스쿨, “코딩 테스트 공부” (https://school.programmers.co.kr/learn/courses/30/lessons/118668), 2026-09-30 조회. ↩