BOJ 11052. [Silver1] 카드 구매하기

[hojongs]

Problem link

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

Problem abstraction

문제의 핵심을 요약한다. 체계적인 문제 접근을 위해, 문제를 추상화한다

적합한 자료구조를 생각한다

n개의 카드팩에 대해 카드가 i개인 카드팩 가격들이 Pi로 주어졌을 때 n개의 카드를 구매하는 최대 가격

Design(Plan) algorithm

# 1

---
# 2

---
# 3

Algorithm idea

추상화한 문제 이해를 기반으로 알고리즘의 대략적인 구현 계획을 서술한다

Pseudo-code

idea를 수도 코드로 작성해본다

Validate algorithm

알고리즘의 유효 여부를 구현 전에 검증한다

예제 입력을 수도 코드로 계산해보고, 놓친 알고리즘 오류가 있는지 확인한다

Impl

import sys

readl = sys.stdin.readline

n = int(readl())
prices = list(map(int, readl().split()))
cache = [0] * (n+1)

def f(nn):
    """
    nn: 사야할 개수
    f(n): n개의 카드 구입 시 최대 가격
    f(n) = max(Pi + f(nn - i) for i in 1...nn)
    """
    if cache[nn] != 0:
        return cache[nn]
    else:
        if nn == 0:
            return 0
        else:
            maxx = 0
            for i in range(1, nn+1):
                maxx = max(maxx, prices[i-1] + f(nn-i))
            cache[nn] = maxx
            return maxx

print(f(n))

Self-feedback

구조적 접근: 문제를 추상화하여 구조적으로 접근했는가?

DP임을 알고 풀면 쉽다

사고력: 알고리즘을 완전히 이해했는가? (충분한 사고력을 가졌는가?)

구현력: 알고리즘을 신속, 정확하게 구현했는가?