[BAEKJOON]24267 카드 구매하기 2

문제 요약

• 알고리즘 분류: 동적계획법, dp
• 난이도: Silver1
• 문제내용:
  • N개가 주어지고 1 부터 N까지의 팩의 개수와 가격이 있다.
  • i번째는 팩개수를 나타내고 팩 개수마다 가격이 붙어 있다.
  • N개 카드를 구입할때 가장 싸게 구입할수있는 가격을 출력해라.

• 사이트: https://www.acmicpc.net/problem/16194

16194번: 카드 구매하기 2

문제풀이

 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수로 풀라면 재귀호출방식으로 해야 하는데 재귀호출시 시간초과가 나오므로 dp로 풀여야 될 문제이다. dp에 관련된 설명은 여기에서 확인해보면된다.  그리고 아래 사이트문제에서 max → min으로만 바꾸면 되기 때문에 아래사이트 문제를 참고 하고 문제 풀이를 보는것을 추천한다.

https://jih3508.tistory.com/137

[BAEKJOON]11052 카드 구매하기

문제 접근방법

 dp는 구현보다 아이디어를 요구하는 문제로서 생각만 한다면 코드 구현은 간단한다. 데이터가 최대 1000개이고 파이썬이 초당 2천만번 연산이 가능하다고 가정할때 O(N ^ 2)까지는 가능하다고 보면된다. 그러면 이중 for문으로 처리가 가능하다.

 어떤식으로 이중 for문으로 점화식을 계산 할거라면 우선 N번째까지 반목문으로 작성한 다음 반복문안에서 또 i번째까지 반복문으로 해서 각 i번째 마다 최소값으로 나올수 있는 수를 저장할것이다. 즉 i 번째 까지 가장 작은 값이 나올수 있는 수는 i번째와 i 에서 i - j까지의 가장 큰값과  j번째 팩 가격을 더한 값중 작은 값은 i번째에 저장하는식으로 진행 하면된다. 점화식을 세우면 아래와 같다.

dp[i] = min(dp[i], dp[i - j] + pack[j])

dp는 i 번째 까지의 최대값 pack은 각 카드 가격이라고 보면된다. 아래 그림은 예제5를 표로 나타낸것이니 참고 해보면된다.

• 0번째 인덱스는 첫번째라서 그래로 넣어 준다.(pack[0])
• 1번째 인덱스는 0번째 인덱스 2번 더하는것 보다 1번째 인덱스 값이 작다.(pack[1])
• 2번째 인덱스는 2번째 인덱스값이랑 1번째 인덱스 3번 더하는것과 0번째 + 1번째 더한것중 2번째 인덱스와 0번째 + 1번째 인덱스 더하는것값이 가장 작다.(pacl[2], pack[0] + pack[1])
• 3번째는 1번째 인덱스 2번 더한것이 가장작다. (pack[1] + pack[1])

Code

Python

N = int(input())
p = list(map(int, input().split()))
dp = [0] * N
dp[0] = p[0]

for i in range(1, N):
    dp[i] = p[i]
    for j in range(i):
        dp[i] = min(dp[i], dp[j] + p[i -j - 1])

print(dp[-1])

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] p = new int[N];
		int[] dp = new int[N];
		for(int i = 0; i < N; i++) {
			p[i] = Integer.parseInt(st.nextToken());
		}
		dp[0] = p[0];
		for(int i = 1; i < N; i++) {
			dp[i] = p[i];
			for(int j = 0; j < i; j++) {
				dp[i] = Math.min(dp[i], dp[j] + p[i - j - 1]);
			}
		}
		System.out.println(dp[N - 1]);		
	}

}