0m1n's Develog

문제 출처 : https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 풀이 전형적인 배낭문제이다. 입력 받은 pair 벡터를 순회하며 값마다 dp 배열을 업데이트 하면 된다. 여기서 for문을 뒤부터 돌린 이유는, 문제 조건에 한 단원에 한 문제를 출제한다. 라고 명시되어 있기 때문이다. for문을 앞부터 돌리면 중복된 값이 계속해서 누적되기 때문에 뒤부터 돌린다. 최댓값을 구하므로, dp[j] 는 dp[j..

문제 출처 : https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 https://www.acmicpc.net/problem/1149 의 응용 문제이다. 기존 문제는 마지막 N번집에서 1번집 고려를 하지 않았지만 이번에는 고려해야 한다. 마지막 집 -> 첫 집 결국 마지막에서 첫 집을 고려해야 하기에, rgb 반복문을 돌려 첫 집을 어디로 선택할지 순회하며 계산하면 된다. for(int rgb = 0; rgb > a..

문제 출처 : https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 DP로 해결하는 문제이다. P1~PN은 card 배열에 넣어주고, dp[i]를 카드 i개를 갖기 위해 지불한 최댓값 이라고 하였다. 모든 경우의 수를 고려해야 할 것 같아서, 각 dp(1부터 N)마다 1부터 i장 이하의 카드팩을 구매하는 경우를 고려하였다. ex) 1장 카드팩을 구매할 경우 dp[N] = dp[N - 1] + card[1] 이다. 2장 카드팩을 구매할 경우 dp[N] ..

문제 출처 : https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 DP로 해결하는 문제이다. 뒤에서부터 탐색하는 방식으로 해결하였으며 앞에서부터 탐색하는 방법도 있다. dp[i]를 i일부터 시작했을때의 최댓값 이라고 하였다. dp는 동적할당을 해주고 문제의 Ti와 Pi는 vector에 넣어주었다. ※ 1차원 배열 동적할당에서, new int[N]뒤에 ()을 붙이면 0으로 초기화 해준다. int *dp = new ..

문제 출처 : https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 DP로 해결하였던 문제이다. 동전의 종류가 주어지고 주어진 금액을 만드는 모든 경우의 수를 세는 문제이다. 점화식은 다음과 같다. for(int i = 0; i T; while (T--){ int dp[10000 + 1] = {0, }; int N; cin >> N; vector coin(N); in..

문제 출처 : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 배낭 알고리즘이라고도 불리는 Knapsack 알고리즘의 대표 문제이다. 여러가지 케이스가 있을때 특정 조건을 만족하는 값, 조합 등을 구하는 문제들이며 대부분 DP로 해결할 수 있다. 이 문제 역시 DP로 해결 할 수 있는데 문제를 요약해보면, 각 물건의 무게(W)와 가치(V)가 주어지고, 배낭의 용량(K)이 주..