목록2016/09/26 (4)
:: ADVANCE ::
BAEKJOON ONLINE JUDGE 2240 자두나무 https://www.acmicpc.net/problem/2240 DP처음에 bottom-up으로 접근했다가 틀려서일단 top-down으로 먼저 풀음 어떤 시간에 어떤 나무에 있을 경우에는 이전에 같은 나무에 있었다가 그대로 기다린 경우, 이전에 다른 나무에 있었다가 옮겨서 지금의 나무에 있는 경우가 존재하므로 이 둘 중에 큰 값을 가져와야 한다. 그리고 지금 있는 나무의 위치에서 자두가 떨어지면 +1, 아니면 그냥 있는 걸로 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #define Max(x, y) (((x) > (y)) ? (..
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