맛있는감귤

문제 : https://www.acmicpc.net/problem/2169출처Olympiad > 한국정보올림피아드 > KOI 2002 > 고등부 1번 N, M의 최대가 1000이므로 완전탐색으로는 무리가 있을 수 있다.또한 좌, 우, 아래의 이동을 잘 해결해주어야한다.나는 재귀로 해결쓰. DP[][][0]은 아래 [1]은 우측, [2]는 좌측을 나타낸다.제일 처음 1,1에서 출발하여 N,M까지 갈 수 있는 모든 경로를 간다.그리고 리턴을 하면서 기준 노드의 좌,우,하에서 리턴되는 값들을 비교해서 큰 값만 저장하게 되면 마지막 1,1에 남는 값이 최대값이 된다. 12345678910111213141516171819202122232425262728#include #define INF -9876543210lo..

문제 : https://www.acmicpc.net/problem/9095출처ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Taejon 2001 PC번 DP로 해결할 수 있는 문제입니다.1부터 4까지만 보면dp[1] = 1dp[2] = 1+1, 2dp[3] = 1+2, 1+1+1, 2+1, 3dp[4] = 1+3, 1+1+2, 2+2, 1+1+1+1, 1+2+1, 2+1+1, 3+1 이렇게 된다. 자세히보면 i번째 값은 i-1, i-2, i-3번째를 합한 값과 같다.12345678910111213#include int main(){ int T; scanf("%d",&T); while(T--){ int N, n[12]; n[0]=0, n[1]=1, n[2]..

문제 : https://www.acmicpc.net/problem/2579첫 번째 계단부터 최대점수를 구하고... 두 번째 계단의 최대점수 구하고.......마지막 계단의 최대 점수를 구하는 DP문제입니다.첫번째 계단을 밟았을 때 최대값은 첫번째 계단을 밟았을 때 받게 되는 점수가 됩니다. sum[1] = step[1]두번째 계단을 밟았을 때 최대값은 첫번째 계단을 밟고 두번째 계단을 밟았을 때 혹은 첫번째 계단을 밟지않고 2단 점프를 했을 때가 됩니다.세번째 계단 또한 두번째 계단을 밟았을 때 혹은 첫번째 계단을 밟고 세번째계단으로 2단점프를 했을 때가 됩니다.N번째 계단은 N-3번째 계단에서 N-1번째 계단까지 2단점프를 한 후, N번째 계단으로 점프를 했을 때 혹은 N-2번째 계단에서 2단점프를 했..

문제 : https://www.acmicpc.net/problem/11052 기초 DP문제입니다. 여느 DP 문제가 그렇듯이 가장 작은 수부터 고려해 점차 큰 수일 때 경우를 고려하는 Bottom-Up 방식으로 풀면됩니다. DP에서 가장 중요한 것은 메모이제이션 그리고 점화식이죠. 예를 들어, 첫 번째 테스트 입력을 보겠습니다.4 1 5 6 7먼저 붕어빵 개수 당 가격을 담고 있는 fish[4] 배열과 각 수의 팔았을 때 가장 큰 값을 가진 배열 sum[4]가 있다고 봅시다. 먼저 붕어빵 한개를 팔때 가장 비싸게 파는 sum[1] = fish[1]가 되겠죠. 그 다음 붕어빵 두개를 팔 때는 두개에 파는 가격 fish[2]와 한 개 값으로 두 개를 파는 경우(sum[1]+fish[1])가 나옵니다. 이 중..

문제 : https://www.acmicpc.net/problem/1890출처Olympiad > Baltic Olympiad in Informatics > BOI 2006 6번 DP로 해결가능한 문제다. 0,0에 1을 넣고 반목문을 돌면서 오른쪽, 아래로 이동 가능한 곳의 값을 더해준다. (dp값은 그 좌표에 도달 가능한 루트의 개수이다.) 유의할 점은 jump값을 더할 때 N의 값을 초과하지 않는지, N-1, N-1 은 연산을 제외 했는지, 경로의 개수를 고려했는지 이 정도 되겠다. 경로의 개수가 많아 BFS로 풀게 되면 메모리 초과가 나오지 않을까 싶다. #include int N; int map[101][101]; long dp[101][101]={0,}; bool visited[101][101];..

문제 : https://www.acmicpc.net/problem/1932 출처 Olympiad > International Olympiad in Informatics > IOI 1994 1번PKU Judge OnlineSphere Online JudgeDP(다이나믹 프로그래밍)로 해결했다. 삼각형 꼭대기 값을 아래 행에 더해주며 최대값을 저장해 마지막에 출력한다. #include #include using namespace std; int N ,max_sum=0;; int num[505][505]; int sum[505][505]={0,}; int main(){ scanf("%d",&N); scanf("%d",&num[0][0]); sum[0][0] = num[0][0]; max_sum = 0; for..

문제 : https://www.acmicpc.net/problem/1149 github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/1149.cpp DP 문제 #include #include using namespace std; int N; int main(){ scanf("%d",&N); int a, b, c; int temp_a, temp_b, temp_c; scanf("%d %d %d",&a, &b, &c); for(int i=0;i