dp

[baekjoon 2011] 암호코드- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net DP개념을 사용하면 되지만, 나름 처리해야 하는 예외들이 몇 가지 있어서 3번째 제출에 맞췄다. 기본적으로 나는 2차원 배열을 이용해서 1. [n][0]에는 결합하지 못하고 그냥 붙는 경우 2. [n][1]에는 결합할 수 있어서 해석의 가짓수가 늘어나는 경우로 나눴다. 1)의 경우는 42 같은 경우이다. 42는 결합되지 못하고 db라는 해석 한 가지밖에 없다. 2)의 경우 26 같은 경우이다. 26은 bf와 z라는 해석 두 가지..

[baekjoon 2579] 계단 오르기 - DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net - 규칙 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 위의 규칙을 통해 두 가지 식을 세울 수 있었다. 1. 도착점 기준으로 생각해보는 경우 도착점 전 계단을 밟고 온 경우 : 연속해서 계단 3개를 밟..

[baekjoon 9095] 1, 2, 3 더하기 - DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net #include using namespace std; int arr[12] = {0, 1, 2, 4, }; int T,n; int dp(int n) { if (n > T; for (int i = 0; i > n; cout

[baekjoon 11726] 2xN 타일링- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 기본 유형의 DP 문제이다. DP는 수학적인 접근이 필요해서 연습이 많이 필요한 것 같다. 또한, 주어진 문제를 작은 문제로 나눠서 푼 뒤, 결과를 통해 문제를 해결하는 것은 분할 정복과 비슷하다. 하지만 분할 정복은 문제를 분할 시 겹치는 문제가 발생하지 않지만 DP는 겹치는 문제들이 발생한다. 따라서 보통 메모이제이션을 이용해서 같은 문제에 대한 결과가 나오는 함수의 호출을 줄여준다. #include using namespace..