본문 바로가기

baekjoon5

[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 1003] 피보나치 함수 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 피보나치 함수의 변형 문제로, f(n)을 호출할 때, f(0)과 f(1)의 횟수를 각각 출력하는 문제 (f = 피보나치 함수) 해석 오늘은 태블릿을 놓고와서 그림은 없다. 이 문제는 처음에 알쏭달쏭하다. 내가 풀어봤던 피보나치 함수는 함숫값만 구하면 됐는데, 호출 횟수를 구하라니? 그리고 사실은 문제가 2개다. 0을 호출하는 횟수와 1을 호출하는 횟수. 그래서 두 문제를 한꺼번에 풀다 보니 헷갈리는 부분이 있다. 하지만 결국 푸는 방식은 완전히 동일하다. 피보나치 함수에서 f[n] = f[n-1] + f[n-2]라는 식으로 풀었던 것처럼, (f(n)에서.. 2020. 3. 22.
[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.
[DP] [BOJ 1463] 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 어떤 자연수 N에 대해서 세 가지의 연산을 할 수 있다. 1. 3으로 나누어 떨어지면 나눈다. 2. 2로 나누어 떨어지면 나눈다. 3. 1을 뺀다. 임의의 자연수는 이 연산을 반복할 경우 1로 만들 수 있다. 어떤 자연수 N에 대해서, 1로 만들기 위한 연산의 최소 횟수를 구하는 문제. 무식하게 접근하기 우선 가장 무식한 방법은 모든 숫자에 대해서 세 가지 연산을 해보는 것이다. 하지만, 각각의 숫자에 대해서 최대 3개의 연산을 할 수 있으므로, 시간복잡도는 $O(3^N)$가 된다. 근데 N = 100,000이므로 절대로 풀 수가 없다. 제출해보니 메모리 초과가 뜬다. .. 2020. 3. 18.

티스토리툴바