:: ADVANCE ::

BAEKJOON ONLINE JUDGE 1520 내리막 길 https://www.acmicpc.net/problem/1520 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include int n, m;int map[510][510];int dp[510][510]; int solve(int y, int x){ int *res = &dp[y][x]; int i; int dy[4] = { -1, 0, 0, 1 }; int dx[4] = { 0, -1, 1, 0 }; int sum = 0; if (*res != -1) return *res; if (map[y][x]

BAEKJOON ONLINE JUDGE 1463 1로 만들기 https://www.acmicpc.net/problem/1463 DP 기본 문제 1234567891011121314151617181920212223242526272829303132333435#include #include #include #define Min(x, y) (x = 0) return dp[n]; if (n

BAEKJOON ONLINE JUDGE 2159 케익 배달 https://www.acmicpc.net/problem/2159 DP 입력 순서대로 좌표와 좌표 인접 지역을 가는 경우의 최소값을 각각 저장해 둔다.dp table [n 번째 입력] [5(0 : 좌표, 1~4 : 좌표 인접지역)] = 거리 최소값 dp[n][i] = min(dp[n - 1][i] + [n - 1][i] 번째에서 [n][i]번째로의 거리) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include #include int n;int beforex, beforey;l..

BAEKJOON ONLINE JUDGE 1328 고층 빌딩 https://www.acmicpc.net/problem/1328 DP dp[n][l][r] -> n : 건물의 수 l : 왼쪽에서 봤을 때 빌딩의 수 r : 오른쪽에서 봤을 때 빌딩의 수n - 1 건물의 수의 상태에서 건물을 추가하여 경우의 수를 구해나가는 과정이때, 길이 n 번째 건물을 추가하여 경우의 수를 따지기보다 길이 1의 건물을 추가한다고 생각하면 점화식을 구하기 쉽다. 예를 들어, 3개의 건물 2, 3, 4가 존재 할 때 l , r234 3, 1324 2, 1243 2, 2342 2, 2423 1, 2432 1, 3 이 경우에 길이 1인 건물을 추가해 보자1. 맨 앞에 추가하기 -> l + 1이 된다. l , r1 234 4, 11 ..

BAEKJOON ONLINE JUDGE 2531 회전 초밥 https://www.acmicpc.net/problem/2531 연속해서 먹을 수 있는 접시가 k 개 이기 때문에 회전(순환)의 경우 배열을 추가로 k개 더 선언하여 뒤에 더 입력하였다. dp로 문제를 풀었다. dp[마지막으로 먹은 초밥의 index] = index의 초밥을 마지막으로 먹었을 경우 최대로 먹은 초밥의 가짓 수 k개 안에 중복되는 초밥번호가 있을 경우 더이상 수를 세면 안되기 때문에 이를 처리해야 한다.초밥의 접시 여부를 판단하는 배열을 선언하여 i 번째 초밥을 추가하면 i - k의 초밥을 빼 준다. 또한 연속으로 초밥을 먹으면서 쿠폰 번호와 동일한 초밥을 먹을 수 있으므로 이를 판단하여야 한다.dp를 채워나갈 때 같이 계산을 하..

BAEKJOON ONLINE JUDGE 7579 앱 https://www.acmicpc.net/problem/7579 DP! 최소의 비용문제의 핵심은 입력 메모리 값을 적절히 조합하여 합이 필요한 메모리 M 이상을 만드는데, 그 중 cost가 가장 작은 값을 출력하는 것이다.단순히 완전히 탐색을 하여 메모리 조합을 찾는 경우에는 당연히 Time Limit가 발생한다.따라서 DP로 문제를 풀어야 하는데처음에는 dp[메모리] = cost(최소값) 로 생각을 하여dp의 index(memory)가 입력 기준을 처음으로 넘는 cost를 출력하려 하였으나 메모리 범위가 넓어 배열을 잡을 수 없다. ---> 반대로!!index와 값을 반대로 하여 보자dp[cost] = memory(최대값) 입력 메모리와 cost를 ..

BAEKJOON ONLINE JUDGE 1915 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 DP!! 풀이 1. 수학 + 구현 1000x1000 이므로 일단 input을 한번씩 탐색하는 것은 가능하다.but, 탐색하면서 정사각형인지를 판단할 때 배열을 다시 탐색하는 일은 아마도 Time Limit이 발생할 것이다.따라서, 정사각형인지를 판단하는 여부를 줄였다. 정사각형의 면적은 한 변의 제곱이다.또한 입력은 0아니면 1이기 때문에 배열에 해당하는 값의 합(면적)이 한 변의 제곱과 같으면정사각형이라고 판단하였다. 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 위 입력에서 표시한 지점의 입력의 합 4이며 변이 2인 정사각형의 면적과 같다. 면적을 구할 때 또..

BAEKJOON ONLINE JUDGE 9095번 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 123456789101112131415161718192021222324252627#include int main(){ int d[11]; int n; int t; scanf("%d", &t); d[0] = 0; d[1] = 1; d[2] = 2; d[3] = 4; for (int i = 4; i

BAEKJOON ONLINE JUDGE 1149번 RGB거리 https://www.acmicpc.net/problem/1149 12345678910111213141516171819202122232425262728293031#include int min(int first, int second){ if (first

dovelet 21 단계 DP SCV 자원채취 / SCV http://59.23.113.171/30stair/scv/scv.php?pname=scv 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include int map[110][110]; int scv[110][110]; int main(void) { int n, i, j; scanf("%d", &n); for (i = 1; i