다이나믹프로그래밍

[Backjoon_11052] 카드 구매하기(Java)

문제링크 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제설명 더보기 더보기 문제 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 전설카드 레드카드 오렌지카드 퍼플카드 블루카드 청록카드 그린카드 그레이카드 카드는 카드팩의 형태로만 구매할..

다이나믹 프로그래밍

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누고 효율적으로 푸는 방법이다. 효율적으로 풀기 위해서는 중복되는 작은문제에 대한 처리를 Memorization을 통해 간단히 해결할 수 있다. 다이나믹 프로그래밍 다이나믹 프로그래밍은 큰 문제를 작은문제로 바꾸어 푸는 것이다. 다이나믹 프로그래밍으로 문제를 해결하기 위해서는 Overlapping Subproblem과 Optimal Substructure라는 두가지 조건을 만족해야한다. 그리고 위의 조건에 의해 불필요하게 중복처리해야하는 문제들이 있다. 이를 해결하기 위해 Memorization을 사용한다. 다이나믹 프로그래밍의 대표적인 예로 피보나치 수열이 있으며 다이나믹 프로그래밍의 두가지 조건과 효율적으로 해결하기 위한 Memoriation을 알아보도록..