DP

문제 : https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 어떤 문제인가? https://codegarden-farmjun.tistory.com/55 [백준(BOJ)] 2293번 동전1 C++ 문제 : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의..

문제 : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 어떤 문제인가? n가지의 동전이 있다. 이 때 n가지 동전을 사용해서 k원을 만드는 경우의 수를 구하는 것이다. 접근 방법 이 문제를 dp를 사용해 접근하였다. 문제의 예시로 알아보자. 1, 2, 5원짜리 동전으로 10원을 만드는 경우의 수다. 1원 1 2원 1 1 2 3원 1 1 1 2 1 4원 1 1 1 1 2 1 1 2 2 5원 1 1 1 1 1 2 1 1 1 2 2 1 5 어떤 규칙..

문제 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 어떤 문제인가? 수열 A 중 가장 긴 증가하는 부분 수열의 길이를 출력하면 된다. 증가하는 부분 수열 = 부분 수열이여야 하고 원소들이 오름차순 이어야 한다. 이 중 길이가 가증 큰 것을 찾으면 된다. 접근 방법 이 문제는 dp를 통해 접근하였다. int arr[1001]; int dp[1001]; n이 100..

문제 : https://www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 어떤 문제인가? 크기가 n인 정수 배열의 부분 배열 중 각 원소들의 합이 가장 큰 부분 배열을 찾아 그 합을 출력하는 문제이다. 접근 방법 일단 이 문제는 dp의 방식으로 접근했다. 코드를 보자. int t; cin >> t; 테스트 케이스의 수를 입력받는다. while (t--) { int n; cin >> n; int arr[n ..

문제 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 어떤 문제인가? 2*n크기의 직사각형을 1*2, 2*1의 타일로 채우는 방법의 수를 구하는 것이다. 간단한 dp문제이다. 접근 방법 n이 1일 때 2*1 타일만을 사용해 한 가지 방법밖에 없다. n이 2일 때 2*1 타일 두 개를 사용하는 방법 1*2 타일 두 개를 사용하는 방법 두 가지 방법 n이 3일 때 세 가지 방법 n이 4일 때 다섯 가지 방법 규칙이 보이는가? n이 3 이상일 때 dp[ n ] = d..

문제 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 어떤 문제인가? 설탕을 n킬로그램을 배달해야 한다. 설탕은 3kg, 5kg 봉지로만 존재해 이 두 가지 종류의 봉지만 사용하여 배달을 해야 한다. 이때, 배달에 필요한 최소 봉지의 개수를 출력하면 된다. 이 문제는 예전에 그리디 알고리즘을 공부할 때 풀었던 문제이다. 지금은 다이내믹 프로그래밍을 공부 중인데 문제가 있어서 이번엔 dp로 풀어보았다. https://codegarden-farmjun.t..

문제 : https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 어떤 문제인가? 이친수라는 문제에서 정의된 이진수들이 있다. n이 입력됐을 때 n자리 이친수의 개수를 출력하면 된다. 접근 방법 일단 문제가 dp(다이나믹 프로그래밍)이라는 것은 문제를 읽으면 알 수 있다. 그러므로 점화식을 세워야한다. n = 1일 때 1 1개 n = 2일 때 10 1개 n = 3일 때 101 100 2개 n = 4일 때 1001 1010 1000 3개 . ...