본문 바로가기

algorithm3

[DP] [BOJ 11052] 카드 구매하기 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 참고 : 이 문제는 막대 자르기 (rod-cutting 문제와 동일한 문제이다.) 문제 카드가 1개, 2개, 3개, ..., N개가 담긴 카드팩이 있을 때, (카드 팩의 가격은 다를 수 있다.) 카드 N개를 가장 비싸게 살 때의 가격을 구하는 문제 해석, 부분 문제, 시간복잡도 그림을 그려보면 "카드 2개를 사는 최대 가격", "카드 1개를 사는 최대 가격" 등의 부분 문제가 중복됨을 알 수 있다. 이를 좀 더 일반화해보자. N개의 카드를 사는 최대 가격은 (1 2020. 3. 25.
[DP] [BOJ 2163] 초콜릿 자르기 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 www.acmicpc.net 문제 N x M 초콜릿을 1 x 1 초콜릿으로 자르는 최소 횟수를 구하는 문제 해석 이 문제는 DP로도 풀 수 있고 수학으로도 풀 수 있는데, 여기서는 DP로 접근해보자. 우선, 초콜릿은 자르면 더 .. 2020. 3. 24.
[DP] [BOJ 1149] RGB거리 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 수직선 위의 N개의 집이 있을 때, 인접한 두 집의 색(R, G, B 중 하나)을 같지 않게 칠하는 최소 비용을 구하는 문제. 무식하게 접근하기 + 중복되는 부분 문제 여느 때처럼 모든 경우를 탐색해 보았을 때, 모든 전체 경우의 수는 2 * 3^N이다. N 2020. 3. 20.

티스토리툴바