https://www.acmicpc.net/problem/11570
난이도(객관적): Platinum V
난이도(개인적): Gold I (BOJ 2618 하위호환)
문제 난이도도 환상인 문제이다. 이 문제는 dp를 사용하여 풀 수 있는데, dp 테이블을 다음과 같이 나타내면 된다.
- dp[i][j] = 상덕이가 현재 i번째 인덱스, 희원이가 j번째 인덱스에 있을 때 드는 힘의 최솟값
일 때, dp[i][j] = min( dp[i][max(i, j) + 1] + 희원 거리 , dp[max(i, j) + 1][j] + 상덕 거리 ) 이 성립한다.
처음 시작할 때는 지금 있는 위치를 정의할 수 없다는 것을 유의한다.
#include <iostream>
#include <math.h>
using namespace std;
#define MAXN 2001
#define INF 2147483000
int N;
int arr[MAXN];
int dp[MAXN][MAXN]; // 1. 상덕 2. 희원
int solve(int l, int r) {
if (l >= N || r >= N) return 0;
int& cache = dp[l][r];
if (cache != -1) return cache;
int nxt = max(l, r) + 1;
int sangduk = l != 0 ? abs(arr[l] - arr[nxt]) : 0;
int hweewon = r != 0 ? abs(arr[r] - arr[nxt]) : 0;
int ans = min(solve(l, nxt) + hweewon, solve(nxt, r) + sangduk);
return cache = ans;
}
int main() {
cin >> N;
for (int i = 1; i <= N; i++) cin >> arr[i];
for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++) dp[i][j] = -1;
cout << solve(0, 0) << endl;
}
'Problem Solving > Else' 카테고리의 다른 글
BOJ 14572 : 스터디 그룹 (0) | 2022.04.08 |
---|---|
LIS 문제를 세그먼트 트리를 이용하여 풀이하는 방법 (0) | 2022.04.06 |
BOJ 1509 : 팰린드롬 분할 (0) | 2022.04.05 |
BOJ 1949 : 우수 마을 (0) | 2022.04.03 |
BOJ 4716 : 풍선 (0) | 2022.04.02 |