[KOI] 백준 2507 - 공주 구하기

https://www.acmicpc.net/problem/2507

발상

단순히 가는 경우면 어렵지 않게 계산할 수 있겠는데 구출하고 돌아와야 한다.

 

다음과 같은 생각을 해볼 수 있다.

 

갔다가 돌아오는 게 아니라 그냥 2명의 사람이 밟는 발판을 겹치지 않게 이동하기

 

이렇게 두면 테이블이 dp[501][501]인 dp 테이블을 구상할 수 있다.

 

위처럼 테이블을 두면 다음과 같은 점화식을 생각해볼 수 있다.

 

f(i, j) := 공주를 구하기 위해 i번째 돌을 밟았고 도망치기 위해 j번째 돌을 밟는 경우의 수(거꾸로)

 

각각 i와 j에 대해 갈 수 있는 발판을 탐색하면서 경우의 수를 더하는 탑 다운 dp를 고려할 수 있다.

유의 사항

다만 이렇게 동적 계획법을 수행하면 주의해야 할 사항이 있다.

1. j는 목적지에 가지 않도록 한다.

조금만 생각하면 쉬운데 j는 돌아오는 발판이므로 목적지를 또 밟으면 모순이다. 오직 i만 목적지에 갈 수 있도록 제한해야 한다. 그래야 i 경로 -> j 경로가 성립된다.

2. 중복 제거

중복 제거도 해야 한다. 예를 들어 현재 재귀가 f(i, j)인 경우 다음 발판을 선택할 때는 max(i, j) 보다 큰 발판을 선택해야 한다. 다시 말하면 i와 j 사이의 발판은 가게 해선 안된다.

 

 

max(i, j) 조건을 걸지 않으면 위 그림의 설명처럼 사실은 하나의 경우인데 2개로 계산되는 경우가 발생한다.

 

위와 같은 상황을 유의해서 재귀를 수행했을 때 i가 목적지에 도착하면 j와의 거리가 가능할 때(목적지 발판에서 j 위치의 발판으로 이동할 수 있을 때) 1을 반환하도록 한다.

결론

유의 사항을 조심하며 다음 점화식으로 동적 계획법을 수행하면 된다.

 

f(i, j) := 공주를 구하기 위해 i번째 돌을 밟았고 도망치기 위해 j번째 돌을 밟는 경우의 수(거꾸로)

 

i와 j에 대해 반복문을 돌면서 갈 수 있는 발판일 때 재귀를 호출해주면 모든 경우의 수를 계산할 수 있게 된다.

 

참고로 나머지 연산의 시간 복잡도는 제곱근인데 문제에서 제시한 나머지는 1000이라 나머지를 하는데 시간이 꽤 많이 소요된다.

 

최적화를 원한다면 계산하는 즉시 나머지 연산을 하지 말고 값이 어느 정도 모인 뒤 (루프를 다 돌았을 때) 나머지 연산을 하면 좋다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n;
int dp[501][501];
int ar[501][3];
const int MOD = 1000;
 
int memo(int idx1, int idx2)
{
  if (idx1 == n) return (ar[idx1][0] - ar[idx2][0]) <= ar[idx1][1];
 
  int &ret = dp[idx1][idx2];
 
  if (ret != -1)
  {
    if (ret >= MOD) ret %= MOD;
    return ret;
  }
 
  ret = 0;
  int min_start = max(idx1, idx2) + 1;
 
  int cur_pos = ar[idx1][0];
  int dist = ar[idx1][1];
 
  for (int i = min_start; i <= n; i++)
  {
    int n_pos = ar[i][0];
 
    if (n_pos - cur_pos > dist) break;
 
    ret += memo(i, idx2);
  }
 
  if (ret > 999) ret %= MOD;
 
  cur_pos = ar[idx2][0];
 
  for (int i = min_start; i < n; i++)
  {
    if (!ar[i][2]) continue;
 
    int n_pos = ar[i][0];
 
    if (n_pos - cur_pos > ar[i][1]) continue;
 
    ret += memo(idx1, i);
  }
 
  if (ret > 999) ret %= MOD;
 
  return ret;
}
 
void solve()
{
  cin >> n;
 
  for (int i = 1; i <= n; i++)
  {
    cin >> ar[i][0] >> ar[i][1] >> ar[i][2];
  }
 
  memset(dp, -1, sizeof dp);
 
  cout << memo(1, 0);
}
 
int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록