처음에 1차원 dp 배열로 풀려고 했는데 답이 잘 안나와서 한참 헤메다가 2차원 배열이 필요함을 알았다. 핵심로직 1. 1차원 dp 로는 풀리지 않기 때문에 각각의 조각에 대한 것을 단계별로 저장을 한다 -> 2차원 배열 2. 점화식은 아래와 같다(위의 사진도 참조) dp[i][x] = dp[i-1][x-1] + dp[i+1][x-1] : (x는 N 으로 가는 수) 3. 위의 점화식은 범위를 생각해서 조각을 나눠야 한다. i == 0 : dp[i][x] = dp[i+1][x-1] 1 N; for (int x = 2; x
[https://www.acmicpc.net/problem/12851](백준 12851 숨바꼭질 2) 이전에 풀었던 [https://www.acmicpc.net/problem/1697](백준 1697(숨바꼭질)) 과 유사한 문제이고 로직은 거의 비슷하다. 핵심로직 위에서 말했듯 기본적인 로직은 이전에 숨바꼭질과 같다. 1.1. x-1, x, x*2 를 탐색하는 BFS 로 풀면 된다. 1.2. 처음으로 도착하는 노드가 최소시간이다. -> 바로 return 시킨다. [https://www.acmicpc.net/problem/1697](백준 1697(숨바꼭질)) 과는 다른 점은 아래와 같다. 2.1. 최소가 나올 수 있는 경우의 수도 구해야 하므로 방문하고 바로 return 을 하는 게 아니라 다시 conti..
백준 1805번 직사각형에서 탈출 핵심로직 좌표평면을 생각하면 편하다. 4 가지 중 최소값을 가져오면 된다. -> x 와 w 사이의 거리, y 와 h 사이의 거리, x 와 y축 사이의 거리, y 와 x 축 사이의 거리 #include #include using namespace std; int x, y, w, h, result; int main() { cin >> x >> y >> w >> h; result = min({x, y, h-y, w-x}); cout
이제 본격적으로 dp 를 공부하면서 만난 첫번째 문제이다. top-down 방식으로 풀기를 원했지만 재귀가 아직 익숙하지 않아 bottom-up 으로 풀었다. 핵심로직은 2가지 이다. 1. 이전의 값을 이용해서 풀어야 한다. 2. 최초로 들어가 있던 값이 최소가 아닐 수 있다. #include #include using namespace std; int dp[3000001]; int X; void dpFunc(int X) { for (int i = 1; i dp[i] + 1) { dp[i * 3] = dp[i] + 1; } if (dp[i * 2] > dp[i] + 1) { dp[i * 2] = dp[i] + 1; } if (dp[i + 1] > dp[i] + 1) { dp[i + 1] = dp[i] +..
