Baekjoon16194 - 카드 구매하기 2(Python)

백준 사이트 16194 - 카드 구매하기 2 문제입니다.

이 글을 보시기 전에 문제를 풀기 위해 충분한 생각을 하셨나요? 답을 안 보고 푸는게 최대한 고민하는게 가장 중요하다고 생각합니다.!!

☑️ 1. 문제

https://www.acmicpc.net/problem/16194

---

☑️ 2. Input , Output

---

☑️ 3. 분류 및 난이도

코딩테스트 준비-기초 : 브루트포스 - 다이나믹프로그래밍 문제입니다.

---

☑️ 4. 생각한 것들

• 크게 2가지 경우로 나눌 수 있습니다. 100팩을 구매한다고 할 때
  1. 들어온 값이 애초에 제일 적은 비용인 경우 (ex 100팩이 1원 )
  2. 그러지 않은 경우는 1팩 가격 + 99팩 가격 , 2팩 가격 + 98팩 가격 … 49팩 가격 + 51팩 가격.. 이런식으로 접근하면 됩니다.

팩의 개수는 최대 10,000이므로 최악의 경우 O(N^2)이라해도 1억이므로 시간내로 풀 수 있다고 생각하였습니다.

또한 범위를 전체 도는게 아닌, 범위의 절반만 도므로 위의 경우보다 더 짧겠지요.

---

5. code

from sys import stdin

n = int(stdin.readline())


def make_dp(size: int) -> list:
    return [0 for _ in range(size + 1)]


def soultion(dp: list, price: list) -> None:
    for i in range(1, len(price) + 1):
        # 1번의 경우. 애초에 제일 적은 비용인 경우를 생각해 초기화
        dp[i] = price[i - 1]
        # 범위의 절반까지 돌면서 위의 점화식을 통해 계산.
        for j in range(1, (i // 2) + 1):
            dp[i] = min(dp[i], dp[j] + dp[i - j])
    print(dp[n])


price = list(map(int, stdin.readline().split()))

dp = make_dp(len(price))
dp[1] = price[0]
soultion(dp, price)

---

6. 후기

• 문제에서 입출력 예제를 많이줘서 오답률이 높지는 않은듯 하네요.

c++로 작성이 필요하거나 도움이 필요하시면 댓글을 작성해주세요.!! 기록용이라 설명이 자세하지 않습니다.