💡문제
ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 같은 힌트를 시험 전에 공지해 주셨다. 내용은 아래와 같다.
- 여러 단원을 융합한 문제는 출제하지 않는다.
- 한 단원에 한 문제를 출제한다. 단, 그 단원에 모든 내용을 알고 있어야 풀 수 있는 문제를 낼 것이다.
이런 두가지 힌트와 함께 각 단원 별 배점을 적어 놓으셨다. 어떤 단원의 문제를 맞추기 위해서는 그 단원의 예상 공부 시간만큼, 혹은 그보다 더 많이 공부하면 맞출 수 있다고 가정하자. 이때, ChAOS 회장 일로 인해 힘든 준석이를 위하여 남은 시간 동안 공부해서 얻을 수 있는 최대 점수를 구하는 프로그램을 만들어 주도록 하자.
입력
첫째 줄에는 이번 시험의 단원 개수 N(1 ≤ N ≤ 100)과 시험까지 공부 할 수 있는 총 시간 T(1 ≤ T ≤ 10000)가 공백을 사이에 두고 주어진다.
둘째 줄부터 N 줄에 걸쳐서 각 단원 별 예상 공부 시간 K(1 ≤ K ≤ 1000)와 그 단원 문제의 배점 S(1 ≤ S ≤ 1000)가 공백을 사이에 두고 주어진다.
출력
첫째 줄에 준석이가 얻을 수 있는 최대 점수를 출력한다.
예제입력
3 310
50 40
100 70
200 150예제출력
220📖내가 작성한 Code
import sys
"""
1. 공부 한다 안한다 0/1 문제
2. 전형적인 배낭문제
"""
def knapsack(limit, array):
dp = {0: 0}
for k, s in array:
temp = {}
for sum_s, sum_k in dp.items():
if dp.get((new_s := s + sum_s), limit) > (new_k := k + sum_k):
temp[new_s] = new_k
dp.update(temp)
return max(dp.keys())
def main():
inputs = map(int, sys.stdin.read().split())
n, t = next(inputs), next(inputs)
study = sorted([(next(inputs), next(inputs)) for _ in range(n)], key=lambda x: x[0], reverse=True)
sys.stdout.write(str(knapsack(t + 1, study)))
if __name__ == "__main__":
main()
✍️풀이과정
전형적인 배낭문제. 따라서 저번에 사용했던 것과 같은 방식으로 풀었다.
그런데 생각보다 시간이 느렸다. 다른 사람 코드를 살펴 보았는데 백트래킹, 최적화등 다양한 방법으로 풀었다.
import sys
def main():
N, T = [int(x) for x in sys.stdin.readline().split()]
K_and_S = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]
dp = [0] * (T + 1)
for k, s in K_and_S:
for t, dp_t, dp_p in zip(range(T + 1), dp, dp[k:]):
if dp_p + s > dp_t:
dp[t] = dp_p + s
print(max(dp))
if __name__ == '__main__':
main()여기서는 dp[t]를 남은 시간이 t일 때 얻을 수 잇는 최대 점수로 정의했다.
따라서 dp는 총 시간 T에 대하여 저장한 것으로, 각 단원에 대해 range(T+1), dp, dp[k:]를 zip 하였다.
t: 남은 시간
dp_t : 현재 dp[t] (남은시간이 T일때 최고 점수)
dp_p : dp[t+k] (남은시간이 t+k일 때의 최고 점수)
만일 남은 시간이 dp[t+k] 인데 추가로 더 공부할 수 있다면 갱신.
배낭 문제들은, testcase에 따라서 속도가 매우 다르다. 따라서
상태 공간이 희소한지 여부 판단:
- T가 작거나 중간 크기라면 간결하고 최적화된 1차원 리스트 DP를 사용하는 것이 일반적
- T가 매우 크거나 도달 가능한 상태가 희소할 것으로 예상된다면, 딕셔너리 기반 DP(혹은 상태 공간 압축 기법)를 사용해 불필요한 상태 업데이트를 줄이는 것이 효과적
그런데 난 항상 딕셔너리 기반 DP가 좋다고 생각하였다. 왜나면 모든 공간을 안봐도 되기 때문이다. 하지만,
- 상수 오버헤드 문제 : 리스트의 단순 인덱스 접근에 비해 오버헤드가 크게 작용
- C 레벨 최적화 : 리스트 기반의 DP는 C 레벨 반복문 최적화로 빠르게 동작
- 상태 공간 밀도 : 전체 크기가 작으면 가능한 모든 상태가 촘촘하게 존재할 가능성이 높다. 따라서 딕셔너리로 찾기 보다는 리스트로 모든 인덱스 순회하는게 python에서는 빠르고 편함
🧠 코드 리뷰
-
정렬 기준 명시: 공부 시간(k) 기준 내림차순 정렬의 이유를 주석으로 설명하면 좋습니다.
-
파이썬 버전 명시: 할당식(왈러스 연산자)을 사용하는 만큼, 최소 파이썬 3.8 이상에서 실행된다는 점을 명시.
-
상태 관리 최적화: dp 딕셔너리의 크기가 커질 경우를 대비한 추가 최적화(예: 이미 limit을 초과한 상태는 배제)를 고려할 수 있습니다.
-
테스트 케이스 및 예외 처리: 실제 환경에서 다양한 입력에 대해 테스트하고, 입력 형식이 올바르지 않은 경우에 대한 예외 처리를 추가하면 좋습니다.
🛠️AI 개선 코드
import sys
# This solution uses a dictionary-based DP approach for the 0/1 knapsack problem
# (BOJ 14728 - 벼락치기). Requires Python 3.8+ for the walrus operator.
def knapsack(limit, items):
# dp: key = accumulated score, value = minimum time required to achieve that score
dp = {0: 0}
for k, s in items:
temp = {}
for cur_score, cur_time in dp.items():
new_score = s + cur_score
new_time = k + cur_time
# Only update if new_time is within limit and improves the time for new_score
if new_time < limit and dp.get(new_score, limit) > new_time:
temp[new_score] = new_time
dp.update(temp)
return max(dp.keys())
def main():
inputs = map(int, sys.stdin.read().split())
n, t = next(inputs), next(inputs)
# Sort items by study time in descending order; this can help prune redundant updates.
items = sorted([(next(inputs), next(inputs)) for _ in range(n)], key=lambda x: x[0], reverse=True)
# Using t+1 as limit because dp indexes represent time used from 0 to t.
result = knapsack(t + 1, items)
sys.stdout.write(str(result))
if __name__ == "__main__":
main()
💻결과
🖱️참고 링크
