혼종 꼬지마루

https://www.acmicpc.net/problem/17070이 문제와 상당히 유사하고, 2019/10/13 - [Algorithms/DP] - [백준] 17070 - 파이프 옮기기에 위 문제의 풀이를 포스팅 하였으니 왜 같다고 생각한지 확인 해보시길... 먼저 이 문제는 dfs로 풀면 아주, 상당히, 시간이 걸릴 문제다. 그렇기 때문에, dfs에 dp를 먹여서 가지도 쳐 주고, 무한 루프도 쉽게 찾을 수 있다. 한번 끝까지 간(범위를 벋어나거나, 구멍에 빠지거나) 한 동전은 돌아오며 그 길이를 저장한다. 즉, 좌표에 끝까지 갔을 경우, 최대 몇번까지 움직일 수 있는지를 저장한다. 한마디로 구멍이나, 범위를 벋어난 동전은 재귀 호출에 return 할때 1, 2, 3....순으로 돌아오는 좌표에 저장..

https://www.acmicpc.net/problem/1103위의 문제와 상당히 유사했고, 한번 유사문제를 풀어봤기 때문에 '음... 이런 느낌으로 풀면 되겠네?' 하고 슥슥 했는데 한번에 통과됨... 풀어놓고도 왜 된거지? 했음 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 일단 이 문제는 dfs + dp의 유형이라고 본다. 한번 탐색했던 경로에 경로의 갯수를 저장, 즉, 끝까지 한번 가면 돌아오는길에 그 포인터에 이전에 갯수를 더해주고 저장한다. 최초에 목적지에 도착한 파이프는 그 지점에서 1개의 경로를 가지기 때문에 1을 return 받는다. 그럼 return 된 1이 이전의 좌표의 visit 배열에 더해주고 저장한다. 바로 이전 점에서 다른 경로를 탐색하고, return 받을 수 있다면 return 받은 값을 더하고 저..

말 그대로 최대 정사각형의 크기를 구하는 문제 주어진 map에서 최대로 정사각형이 되는 크기의 너비나 높이를 구하면 됨 1. map을 순회하면서 dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]의 최소 값을 구한다 - 이유는 저 3개의 포인트는 각각 정사각형의 크기를 가진 값을 저장하기 때문 - 하나라도 작으면 작은 사이즈의 정사각형을 넣어 주어야 하기 때문이다.ex) 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 ----->>>>> 0 1 4 1 0 0 1 1 1 0 0 1 4 4 0 0 1 1 1 0 0 1 4 9 0 2. 최소값의 너비나 높이를 구하기 위해 sqrt해주고, +1해 준 뒤 다시 제곱하여 dp[i][j]에 넣어준다. 3. 시간 복잡도는 O(N^2)이..

기존 값을 저장하고, 그걸 불러와야 답을 구할 수 있다... 그래서 메모이제이션이 중요하기 때문에 DP라고 생각함 1. 순차적으로 map을 검사하면서 방문하지 않은 지점이라면 DFS로 탐색 2. 방문한 지점이라면 그 방문한 지점의 값을 반환 3. 이렇게 끝까지 같다가 돌아오면 리턴된 값과 답을 비교하여 답을 찾아준다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #define MAXSIZE 1002using namespace std; char map[MAXSIZE][MAXSIZE];int visit[MAXSIZE][MAXSIZE];int dx[] = { 0, 0, -1, 1 };int ..

dp를 처음 시작하면서 이 문제를 꼭 풀어보면 좋다고 생각하는 문제 dfs로 검사하며 return하는 과정에서 메모이제이션을 해주는 문제로 필수문제라고 생각 1. 맵정보를 입력받으며 dp를 -1로 초기화 2. dfs로 내리막길을 찾으며 탐색 그 위치에서의 dp는 방문한 것을 체크하기 위해 0으로 만든다. 3. 도착점에 도착하면 1을 반환한다. 4. 만약 방문한 점이고, dp가 -1이 아니라면 그 지점의 값을 반환한다. 123456789101112131415161718192021222324252627282930313233343536#include #define MX 503using namespace std; int map[MX][MX], dp[MX][MX];int dx[] = { 0, 0, -1, 1 };..

dp문제 중에 무조건 풀어야하는 기초문제인 것 같습니다. 한 열에서 스티커를 선택하지 않을 경우, 첫번째 행의 스티커를 선택할 경우, 두번째 행의 스티커를 선택할 경우로 나누어 이전 열에서 가장 큰 값을 더해주는 식으로 dp를 풀어주면 N번 연산으로 끝낼 수 있습니다. 12345678910111213141516171819202122232425262728293031#include #define SIZE 100003#define MAX(X, Y) ((X) > (Y) ? (X):(Y))using namespace std; int map[3][SIZE], dp[3][SIZE];int T, N; int main(void){ cin >> T; while (T--) { cin >> N; for (int i = 1; ..

전형적인 DP문제 입력을 받으며 DP배열의 (r - 1, c), (r, c - 1), (r - 1, c - 1) 중 가장 큰값을 현재 입력되는 위치의 사탕개수를 더해주면 끝 123456789101112131415161718192021#include #define MXSIZE 1002#define MAX(X, Y) (X) > (Y) ? (X) : (Y)using namespace std; int map[MXSIZE][MXSIZE], dp[MXSIZE][MXSIZE];int N, M; int main(void){ cin >> N >> M; for (int i = 1; i map[i][j]; dp[i][j] = MAX(dp[i - 1][j - 1], MAX(dp[i - 1][j], dp[i][j - 1]));..

삼성 기출문제 퇴사랑 같은 문제지만, 범위가 넓어서 DP로 푸는게 맞음 그냥 퇴사문제는 범위가 좁아서 DFS로도 풀 수 있지만 이 문제는 범위가 1500000이나 되기 때문에 DFS로는 절대 풀 수 없다 DP를 처음 공부하고 퇴사, 퇴사2를 풀면서 마스터했다 1. 일을 하고 다음 날 돈을 받는 걸로 생각한다 ex. 3일 일하고 4일째 돈을 받는다. 따라서 N일까지 일을 한다고 가정할 때, N+1일날 돈을 받는다. 2. 오늘 부터 일을 할 때, map[i].day 이후, 즉 i + map[i].day 가 >N + 1일때는 일을 할 수 없으므로 continue; 3. i+map[i].day 되는 날 최대 값을 dp에 저장하고, 갱신하며 N + 1일까지 일을 한다. 123456789101112131415161..