:: ADVANCE ::

BAEKJOON ONLINE JUDGE 1535 안녕 https://www.acmicpc.net/problem/1535 0-1 knapsack 문제체력이 100까지므로 100에서 깎아도 되고0에서 인사를 할 때 체력을 쌓아서 100이전, 99로 만들때 저장되는 기쁨의 최대값을 출력 strength[1]을 사용할 때 모든 체력에 저장된 기쁨에 joy[1]을 합해가면 점차 쌓여서 체력 99에 모든 값이 저장되어 있다. 12345678910111213141516171819202122232425262728293031#include #define Max(x, y) (((x) > (y)) ? (x) : (y)) int n;int strength[20], joy[20];int dp[100]; int main(){ i..

BAEKJOON ONLINE JUDGE 2411 아이템 먹기 https://www.acmicpc.net/problem/2411 DP이동은 오른쪽, 위쪽만 가능하다 -> scv 문제와 비슷아이템을 모두 먹어야 한다 -> 아이템을 먹으러 들려야 한다. 아이템 있는 곳으로 갈 때는 한 아이템에서 다른 아이템이 있는 위치로 이동하는 부분 경로, 부분 이동 경우의 수로 생각. 최종적으로는 각 아이템을 먹으러 이동하는 부분 경로를 곱하면 된다. 장애물이 있는 곳은 못가는 곳이므로 경로값 0오른쪽, 위쪽만 가능하므로 시작 지점의 왼쪽과 아래는 갈 수 없는 부분. 경로값 0시작은 (1, 1), 마지막은 (n, m) 그리고 C++에서 vector를 쓸 때, >>에서 꼭 사이를 띄어주어야 컴파일 에러가 나지 않는다. 매번..

BAEKJOON ONLINE JUDGE 11052 붕어빵 판매하기 https://www.acmicpc.net/problem/11052 DPdp[n] = Max(i개 세트 가격 + 나머지 붕어빵 개수의 최대값) 1. top-down 12345678910111213141516171819202122232425262728293031323334353637#include #define Max(x, y) (((x) > (y)) ? (x) : (y)) int n;int cost[1001];int dp[1001]; int solve(int num){ int i; if (num == 0) return 0; if (dp[num]) return dp[num]; dp[num] = cost[num]; for (i = 1; i

BAEKJOON ONLINE JUDGE 11507 오르막 수 https://www.acmicpc.net/problem/11057 오르막 수1. dp[ n 번째 수가 ] [ i 일 때 ] 오르막 수 = n - 1번 째수가 i보다 같거나 큰 수들의 오르막 수들의 합 즉, 5자리 수 일 때 첫째 자리에 1이 오면 두번째 자리에 1, 2, 3, .... 9가 올 수 있고, 이 수들을 처음 수로 하는 4개의 오르막 수들이 다 올 수 있기 때문에 모든 그러한 경우의 수들을 다 합하면 된다. 12345678910111213141516171819202122232425262728293031323334353637#include int n;int dp[1001][10]; int solve(){ int i, j, k; int..

BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2005 2591 숫자카드 https://www.acmicpc.net/problem/2591 DP dp 이전까지 배치된 카드에 새로 추가된 수(한자리) 카드를 놓으면 된다. 10

BAEKJOON ONLINE JUDGE 2184 김치 배달 https://www.acmicpc.net/problem/2184 DPDP 테이블을 설정하기에 앞서문제를 잘 파악하면 배달을 하기위한 움직임이 왼쪽으로 이동, 오른쪽으로 이동 밖에 없으며,가는 길에 배달할 지역을 뛰어넘는 (예를 들어 10에서 출발, 9을 들리지 않고 1을 먼저 배달하는) 경우는 발생하지 않는다는 점을 알아야 한다.따라서 DP 테이블을 구간으로 잡을 수 있는데 먼저, DP[left][right] 에서 left - right 범위 내 위치한 배달할 지역은 이미 배달을 완료한 상태로 최적화가 될 수 있다.따라서 처음 공장 위치를 시작으로 범위를 점차 넓혀 나가는 식으로 탐색해 나간다. 또한 주의할 점이 하나 더 있다. 예를 들어 10..

BAEKJOON ONLINE JUDGE 11726 2xn 타일링 https://www.acmicpc.net/problem/11726 DP 만들 수 있는 경우를 직접 만들어 보면 규칙을 찾을 수 있다. 이전 경우에서 | 막대 하나를 더 추가하는 경우와 이전, 이전 경우에서 = 막대를 추가하는 경우따라서 dp[i] = dp[i - 1] + dp[i - 2] (피보나치 수열과 같은 식)을 얻을 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include #define Max(x, y) (x > y ? x : y) int n, m;int dp[1002][1002];int map[1002][1002]; int s..

BAEKJOON ONLINE JUDGE 11048 이동하기 https://www.acmicpc.net/problem/11048 1234567891011121314151617181920212223242526272829303132333435363738#include #include #define Max(x, y) (x > y ? x : y) int n, m;int dp[1002][1002];int map[1002][1002]; int solve(int y, int x) { int *res = &dp[y][x]; if (*res != -1) return *res; if (map[y][x]

BAEKJOON ONLINE JUDGE 2228 구간 나누기 https://www.acmicpc.net/problem/2228 DP 구간을 나눌 때 예를 들어 예제를 살펴보면 6개의 원소 중 2개의 구간을 만들어야 한다.이때 위의 조건을 만족하면서 합이 최대가 되는 경우는 { -1, 3, 1, 2, 4, -1 } 인 경우이다. 이 문제를 DP로 풀 때DP[n][m] = n개의 원소들의 집합에서 m개의 구간으로 나누었을 때 합의 최대값 1. i번 째 수를 포함하지 않는 경우 이는 i - 1까지의 원소들의 집합에서 구간 m개를 나눈 합의 최대값과 같다. -> dp[i][m] =dp[i - 1][m] 2. i번 째 수를 포함하는 경우i번 째 수를 포함하는 구간이 m번째 구간이 되어야 하며이전에 m - 1구간을..

BAEKJOON ONLINE JUDGE 1937 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1. Bottom up 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include #include #include using namespace std; struct Point { int x, y; int value;}; bool cmp(const Point &first, const Point &second) { return first.value