백준 dp

https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 1. 왼쪽 카드만 버리는 경우 2. 왼쪽 카드와 오른쪽 카드를 버리는 경우 3. "왼쪽 카드 < 오른쪽 카드" 를 만족하여 오른쪽 카드만 버리는 경우 이 세가지 경우를 모두 고려해주어야 한다. dp[left][right] 는 왼쪽 카드와 오른쪽 카드를 left장, right장 버렸을 때 점수의 최댓값이다. 코드는 다음과 같다. #include #include using ..

https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 배낭 문제랑 똑같은 문제이다. 배낭문제는 2차원 Dp를 이용해서 Buttom-up으로 풀었었는데 배낭문제는 1차원 Dp를 이용하면서 Top-down으로 풀어주는게 더 효율적이다. 배낭문제를 풀어본 사람이라면 알다시피 2차원 배열에서 굳이 값을 채우지 않아도 되는 배열까지 값을 채우기 때문에 메모리와 시간이 Top-down에 비해 오래걸린다. 주어진 시간..

https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net DP문제로 아주 유명한 문제이다. DP가 큰 문제를 작은 문제로 나눠 생각해서 작은 문제를 통해 큰 문제를 해결하는 방식이므로 문제를 쪼개야한다. 예를 들어 1000원을 만드는 방법의 수를 구해야 한다면, 주어진 동전으로 1원을 만드는 경우의 수, 2원을 만드는 경우의 수, 3원을 만드는 경우의 수... 계속 나아가서 1000원까지 도달하는 방식으로 DP를 구성해 주면 된다...

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 딱봐도 DP문제이다. 실버DP문제는 꽤 많이 풀어서 그런지 풀이가 한눈에 보인다. 해당 스티커를 선택할 수 있는 경우를 모두 고려해서 최대값을 dp값으로 저장하면 된다. 위의 경우를 점화식으로 작성하기만하면 끝이다. 스티커가 2줄이라 2차원 배열 쓰면 끝. 코드는 다음과 같다. #include #include #include #include #include #include #includ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 퇴사를 하기 전까지 최대 수익을 내야하는 문제이다. 실버3이지만 앞에서 미리 포스팅했던 포도주 시식이나 RGB거리 등 다른 Dp문제보다 더 애먹었다. Dp 문제를 접하는 마인드로 일단 어떻게든 다 훑어야지 라고 생각하며 접근했는데...처음 2중for문으로 점화식을 짰는데...예외 상황이 너무 많아서 하나씩 예외처리를 하다보니까 코드가 Greedy하게 변했다. 결국 풀다가 시간이 너무 지나서 작성했던 코드 다지우고 담날에 새로 하자는 마인드로 그냥 잤다 ㅋㅋ 담날에 수업시간에 잠깐 봤는데 어떻게 탐색해야할지 새로운 아이디어가 떠올라서 ..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제를 처음 봤을때 DFS 쓰는 문제인가? 했는데 DFS를 사용해도 답은 나오겠지만 너무 가짓수가 많아서 시간초과에 걸릴게 뻔했다. 숫자들이 규칙이 없는것이 아니라 1차이라는 규칙이 있으므로 그냥 Dp썼다. Dp를 점점 하면서 느낀거지만 문제가 다 똑같다. 물론 아직 Dp애기 수준이라 실버1 언저리 문제만 풀지만, 현재까지 느낀바로는 그렇다. 문제 풀이는 각 자릿수를 정해야하는데 첫번째 자릿수에는 0이 올수 없고, 앞자릿수에 영향을 받지 않으므로 미리 세팅을 해준다. dp[0][0]을 제외하고 나머지를 모두 1..