dp
-
[BOJ] #14501 _ 퇴사Problem Solving/BOJ 2019. 8. 28. 21:25
[퇴사] https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dfs를 이용하여 모든 경우의 수를 해보고, 최대 수익을 구하였다. 찾아보니 DP를 이용해 풀 수도 있다. [ 소스 코드 ] #include #include #define MAX 15 using namespace std; int N, T[MAX + 1], P[MAX + 1]; int result = 0; void solve(int day, int TotalPrice); int main() { scanf("%d", &N); for (int i = 1; i N) { result = max(result, TotalPrice); r..
-
[BOJ] #9465 _ 스티커Problem Solving/BOJ 2019. 8. 12. 22:34
[스티커] https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net 아주 간단한 DP문제이다. 100점인 스티커를 기준으로 가능한 경우는 아래와 같이 3가지다. 이를 이용하여 점화식을 만들 수 있..
-
[BOJ] #2156 _ 포도주 시식Problem Solving/BOJ 2019. 7. 3. 19:25
[포도주 시식] https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net DP를 사용하는 문제이다. DP (Dynamic Programming) 이란? 복잡한 문제를 간단한 여러개의 문제로 ..