def recursive (index, output) {
If ( 탈출 조건 with index ) {
재귀함수에서 빠져 나와야 하는 기저사례
}
반복문 ( 부모가 여러 개 있을 경우 반복문 사용함. 부모가 한 개나 두 개인 경우 필요 없음 )
{
If ( /* 탐색하지 않아도 되는 부분들 */ ) continue
recursive 함수 호출 (자식 탐방일 수 있고 상대 탐방일 수 있다)
}
부모로 돌아갈 때마다 해야될 일 (보통은 부모의 상태로 복원해야 하는 코드)
해당 경우의 수 마지막 부분까지 온 경우이므로 마지막 자식 호출하고 난 다음에 해야될 일 (보통 계산)
}
② 각 방에는 음의 정수 또는 양의 정수가 있다. 왕자가 이동할 때 이 숫자에 영향을 받는다.
음수라면 숫자만큼 체력이 삭감되고, 양수라면 숫자만큼 체력이 상승한다.
③ 왕자 체력이 0 이거나 음수가 되면 게임은 종료된다.
2.문제예제
3.팩트추출
Fact 1: N X M 던전판을 작게 축소하여 작은 문제들의 결합으로 구성할 수 있고 이 작은 문제들의 최적해들을 결합하면 전체 문제의 최적해가 된다. 따라서 Dynamic Programming 문제이다.
Fact 2:dp[i,j] 를 dungeon[i,j] 에서 최소값이라고 할 때, dp[i,j] 는 dp[i,j+1] 과 dp[i+1,j] 중 최소값에 dungeon[i,j] 를 더한 값이다. dungeon[i,j] 값이 양수라면 0을 음수라면 절대값을 더한다. 문제에서 최소값을 구하라고 명시하고 있으므로 양수일 때는 신경 쓸 필요가 없다. 음수를 다 더한 값이 그 경로의 최소값이 된다.
Fact 3 : 일반적인 DP 문제와는 달리 해당 점화식에서 바로 값을 구할 수 없다. 점화식으로 표현되는 dp[i,j+1] , dp[i+1,j] 이 두 항이 다른 값들이 먼저 계산되어야 계산할 수 있기 때문이다. 그래서 기저 사례부터 먼저 구하고, 기저 사례만 필요한 마지막 행과 열을 구해 나머지 부분들을 계산하여야 한다.
Fact 4: Top-Down 방식이던 Bottom-Up 방식이던 무한 루프를 방지하기 위해 기저 사례가 필요하다. 점화식으로 표현된 dp[i,j+1] 과 dp[i,j+1] 이 두 항이 이전 항들로 표현되지 않을 수 있을 때 기저 사례라고 한다. 이 문제에서는 공주가 있는 위치가 기저 사례이다.
4.문제풀이(수동)
예제 1번을 기준으로 문제풀이를 진행한다.
기저 사례를 먼저 구하면, 공주 위치에 있는 값이 -5 이므로 6 이라는 최소 체력이 필요하다.
(만약 값이 양수였다면 1 이라는 최소 체력이 필요할 것이다.)
Fact 3 에서 정리한 바와 같이 공주 위치를 기준으로 좌측 행 상단 열을 구하면 다음과 같다.
마지막 행과 마지막 열은 각각 이전 행과 이전 열 한 개씩만 필요하기 때문에 풀 수 있다.
max(1, -3+5) = 2
max(1, -1+6) = 5
max(1, -10+1) = 1
max(1, -30+6) = 1
max(1, 5+1) = 6
이 값들을 기준으로 나머지 부분들도 계산하면,
max(1, 2+min(5, 6)) = 7
max(1, 3+min(2, 11)) = 5
max(1, -3+5) = 2
max(1, 5+min(11, 1)) = 6
max(1, 10+min(5, 1)) = 11
max(1, -1+6) = 5
max(1, -10+1) = 1
max(1, -30+6) = 1
max(1, 5+1) = 6
최소 체력은 7 이라는 것을 알 수 있다.
5.문제전략
위 수동풀이처럼 공주님 위치에서 마지막 행 열을 구한 후, 나머지 부분들을 계산할 수 밖에 없다.
Top-Down 방식, Bottom-Up 방식으로 모두 풀 수 있다.
6.소스코드
Top-Down
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int row_size = dungeon.size();
int column_size = dungeon[0].size();
vector<vector<int>> dp(row_size, vector<int>(column_size));
return calculate(dungeon, 0, 0, dp);
}
int calculate(vector<vector<int>>& dungeon, int i, int j, vector<vector<int>>& dp) {
// 기저 사례
if (i == dungeon.size() - 1 && j == dungeon[0].size() - 1)
return dungeon[i][j] > 0 ? 1 : -dungeon[i][j] + 1;
// 메모이제이션
if (dp[i][j] != NULL)
return dp[i][j];
// 마지막 행
if (i == dungeon.size() - 1)
return dp[i][j] = max(1, calculate(dungeon, i, j + 1, dp) - dungeon[i][j]);
// 우측 마지막 열
if (j == dungeon[0].size() - 1)
return dp[i][j] = max(1, calculate(dungeon, i + 1, j, dp) - dungeon[i][j]);
return dp[i][j] = max(1, min(calculate(dungeon, i + 1, j, dp) - dungeon[i][j],
calculate(dungeon, i, j + 1, dp) - dungeon[i][j]));
}
}
Bottom-Up
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int r=dungeon.size();
int c=dungeon[0].size();
vector<vector<int>> dp(r,vector<int>(c));
for(int i=r-1;i>=0;--i)
{
for(int j=c-1;j>=0;--j)
{
if(i==r-1 && j==c-1) // 초기 값으로 맨 오른쪽 밑 (Princess Cell)
dp[i][j] = max(1,-dungeon[i][j]+1);
else if(i==r-1) // 마지막 행
dp[i][j] = max(1, dp[i][j+1]-dungeon[i][j]);
else if(j==c-1) // 우측 마지막 열
dp[i][j] = max(1, dp[i+1][j]-dungeon[i][j]);
else
dp[i][j] = max(1,min(dp[i][j+1],dp[i+1][j])-dungeon[i][j]);
}
}
return dp[0][0];
}
};
문제풀이부분경로는순차적이며중간경로를건너뛸수있다는특징을가지고있다. 예를들어 1번 2번 3번 … N번까지차례대로베거나, 1번에서 N번으로바로벨수있다.
4. 문제풀이(수동)
dp[i] : i 번째 나무를 높이 1로 만드는데 필요한 최소비용
a[i] : i 번째 나무 높이 , b[j] : j 번째 나무충전비용이라고할때,
점화식은dp[i] = min(1<j<i) dp[j] + a[i]b[j]와같다. 이때 i 는 1부터 N까지이다.
다음은예제입력 2번을기준으로수동풀이이다.
dp[0] = 0
dp[1] = dp[0] + a[1]b[0] = 0 + 2*6 = 12
dp[2] = dp[0] + a[2]b[0] = 0 + 3*6 = 18
= dp[1] + a[2]b[1] = 12 + 3*5 = 27
dp[3] = dp[0] + a[3]b[0] = 0 + 10*6 = 60
= dp[1] + a[3]b[1] = 12 + 10*5 = 62
= dp[2] + a[3]b[2] = 18 + 10*4 = 58
dp[4] = dp[0] + a[4]b[0] = 0 + 20*6 = 120
= dp[1] + a[4]b[1] = 12 + 20*5 = 112
= dp[2] + a[4]b[2] = 18 + 20*4 = 98
= dp[3] + a[4]b[3] = 58 + 20*3 = 118
dp[5] = dp[0] + a[5]b[0] = 0 + 30*6 = 180 ---> ①
= dp[1] + a[5]b[1] = 12 + 30*5 = 162 ---> ②
= dp[2] + a[5]b[2] = 18 + 30*4 = 138 ---> ③
= dp[3] + a[5]b[3] = 58 + 30*3 = 148 ---> ④
= dp[4] + a[5]b[4] = 98 + 30*2 = 158 ---> ⑤
따라서정답은 138 이다. 계산은 15번소요되었다.
5. 문제전략
위수동풀이처럼순수 DP(점화식)로푼다면, O({N*(N-1)}/2) 복잡도가발생한다.
문제에서 N 이 100,000 이기때문에시간제한(2초) 이내에풀수없다. 다른전략이필요하다.
Solving Strategy Item 1 :
dp[i] = min(1<j<i)dp[j] + a[i]b[j]점화식에서 변화하지 않는 부분 a[i] 를 이용한다.
a[i] 부분을 x 로 치환하면 y = bx+c 꼴 일차방정식으로 표현할 수 있는데
a 는단조증가 b 는단조감소이기때문에 마치 볼록한 껍질 형태의 그래프들로 표현할 수 있다.
convex hull 이라고부른다. 예제 입력 2번을 실제 그래프로 표시해보자.
convex hull 그래프 이미지
예제 입력 2번 그래프
4번 문제풀이(수동) 을 자세히 보면 ① ② ③ ④ ⑤ 번 함수들이 계속 반복되는데 이 함수들을 그래프로 표시하면 위 그래프와 같다. 여기서 특징점들이 보인다.
파랑색 함수는 비교대상이 아니라는 점이다. 녹색 함수와 빨간 함수들만 보면 어느 X 값이라도 최소값을 확인할 수 있다.
일차함수이고 기울기가 낮아지는 함수들이다보니, 두 함수의 교점 X 좌표들을 비교만 해보아도 제외 대상을 가려낼 수 있다. 다시 말해 A 함수와 B 함수의 교점보다 B 함수와 C 함수의 교점이 낮다면 B 함수는 볼 필요 없는 것이다.
필요 없는 함수들을 제외하면서 그래프들의 교점들을 모아 두었다가 그 교점들과 A[i] 즉 x 값을 비교한다. x 값이 커질 때의 함수를 찾으면 x 값을 대입하여 y 값을 구할 수 있다.
Solving Strategy Item 2 :
그래프의 교점들과 비교할때이분탐색을이용하면 O(NlogN) 시간복잡도까지줄일수있다.
Solving Strategy Item 1번을 통해 교점들 x 좌표가 오름차순으로 정렬이 되기 때문에 순차적으로 값을 찾기 보다는 이분탐색으로 찾는 것이 훨씬 빠르다.
6.소스코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 100000;
// 일차 함수 표현 : f(x) = ax+b
struct Line {
long long a, b;
double cross_x;
Line(long long a_, long long b_, double cross_x_ = 0) :a(a_), b(b_), cross_x(cross_x_) {}
};
// 두 함수의 교차점
double cross(const Line& f, const Line& g)
{
// f 를 f.ax+f.b 라 하고, g 를 g.ax + g.b 라 할 때 x 를 왼쪽에 남겨두고 이항하면,
return (g.b - f.b) / (f.a - g.a);
}
// 이분 탐색
int binary_search(vector<Line>& line, long long key)
{
int position = 0;
int left = 0, right = line.size() - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (line[mid].cross_x < key) {
position = mid;
left = mid + 1;
}
else
right = mid - 1;
}
return position;
}
long long dp[MAX];
int main()
{
// 입력 예제 2번
int n = 6; // N 나무
vector<int> a = { 1,2,3,10,20,30 }; // 나무 높이
vector<int> b = { 6,5,4,3,2,0 }; // 충전 비용
vector<Line> line_stack;
// dp[0] 은 항상 0 이므로, 1부터 시작
for (int i = 1; i < n; ++i)
{
// 나무가 N 개이면, N-1 개의 점화식이 존재함
Line g(b[i - 1], dp[i - 1]); // y = ax+b 에서 차례대로 (a, b)
while (line_stack.size() >= 1)
{
g.cross_x = cross(g, line_stack.back());
if (g.cross_x < line_stack.back().cross_x) // 교점을 통해 비교. 위에 있는 함수는 버림.
line_stack.pop_back();
else
break;
}
line_stack.push_back(g);
int x_position = 0;
x_position = binary_search(line_stack, a[i]);
// y 값 계산
dp[i] = line_stack[x_position].a * a[i] + line_stack[x_position].b;
}
cout << dp[n - 1] << endl;
return 0;
}
