💡문제
요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.
PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.
- 전설카드
- 레드카드
- 오렌지카드
- 퍼플카드
- 블루카드
- 청록카드
- 그린카드
- 그레이카드
카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.
민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.
예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.
P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.
마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.
카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.
입력
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)
둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
출력
첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.
예제입력
4
1 5 6 7예제출력
10📖내가 작성한 Code
import sys
# 문제 설명
'''
카드팩의 형태로만 구매
카드팩 종료 1개가 포함된 카드팩 ... N개가 포함된 카드팩
가격은 i개가 포함 되면 P(i)원
최댓값 구하기
'''
def make_max_price(number, lst):
if number == 1:
return lst[0]
max_price_of_card_pack = [0] + lst + [0] * (number - len(lst))
for num in range(2, number+1):
combination = []
for num1 in range(1, num//2 + 1):
combination.append(max_price_of_card_pack[num1]+max_price_of_card_pack[num-num1])
max_price_of_card_pack[num] = max(max_price_of_card_pack[num], *combination)
return max_price_of_card_pack[-1]
def main():
speed_input = sys.stdin.readline
number_of_cards = int(speed_input())
price_of_card_pack = list(map(int, speed_input().split()))
print(make_max_price(number_of_cards, price_of_card_pack))
if __name__ == '__main__':
main()
✍️풀이과정
이렇게 긴 문제는 먼저 정리부터 한다. 따라서 주석으로 정리해둠.
처음에는 이중 반복문으로 해도 되나 했는데, N이 1000개라 2번 돌려도 문제 없을듯 해서 해봄.
작은 답으로 큰 답을 만드는 DP문제이므로 그냥 전부 해주면 됨.
코드 리뷰 봤는데, 리스트를 사용해서 한번에 max 하는거 보다는 하나하나 max하여 즉시 업데이트 하는 방식이 메모리 사용도 줄이고 실행시간을 단축 시킬 수 있다고 한다.
리스트 생성 후 값 추가, 마지막에 max 함수(언패킹까지)의 총 오버헤드 생성> 반복문에서의 max 함수의 오버헤드 생성
둘 다 O(n) 시간 복잡도를 가지고 있지만, 상수 시간에서의 오버헤드 차이가 있다.
- 메모리 효율성 : 각 카드 수마다 가능한 모든 조합을 리스트에 저장하면, 특히 카드 수가 클 경우 많은 메모리를 소모
- 시간 효율성 : 리스트에 모든 조합을 추가한 후 max 함수를 호출하면, 리스트의 크기에 비례하여 시간이 소모
🧠 코드 리뷰
-
구현 : 현재는 num == 1인 경우를 별도로 처리하고 있습니다. 하지만 동적 계획법의 일반적인 구현에서는 모든 경우를 하나의 루프 안에서 처리할 수 있습니다. 이렇게 하면 코드가 더 간결해지고, 예외 처리가 줄어듭니다.
-
불필요한 리스트 사용 줄이기 : combination 리스트를 사용하지 않고, current_max 변수를 통해 최대 값을 직접 계산하면 메모리 사용을 줄이고, 속도도 향상될 수 있습니다.
-
인덱스 초과 방지 : 만약 len(lst) < number인 경우, 패킹할 수 없는 카드 수에 대해 0을 채우고 있습니다. 이는 문제의 조건에 따라 적절할 수 있지만, 일반적인 상황에서는 불완전한 입력에 대한 처리가 필요합니다.
🛠️AI 개선 코드
import sys
def calculate_max_price(number, prices):
# dp[i]는 i개의 카드를 구매할 때의 최대 가격
dp = [0] * (number + 1)
# 가격 리스트를 1-based로 맞추기 위해 첫 번째 요소에 0을 추가
for i in range(1, len(prices) + 1):
dp[i] = prices[i - 1]
# 모든 카드 수에 대해 최대 가격 계산
for num in range(1, number + 1):
for j in range(1, num // 2 + 1):
dp[num] = max(dp[num], dp[j] + dp[num - j])
return dp[number]
def main():
input = sys.stdin.read
data = input().split()
number_of_cards = int(data[0])
price_of_card_pack = list(map(int, data[1:1 + number_of_cards]))
print(calculate_max_price(number_of_cards, price_of_card_pack))
if __name__ == '__main__':
main()
💻결과
🖱️참고 링크
