PS/Codeforces

CF Round 994 (Div.2) - D

Polariche 2025. 1. 12. 13:25

D

https://codeforces.com/contest/2049/problem/D

 

문제 정의

(shift 연산의 편의를 위해, 0-index 좌표로 치환하였다.)

 

$ N, M $ 크기의 cost 배열 이 주어진다. 

(0,0) 에서 출발하여, 오른쪽 혹은 아래 방향으로 이동한다. 이 때, $ (0,0) $ 에서 $ (N-1,M-1) $ 까지 이동하는 데에 드는 cost 를 최소화해라.

이동 전, 각 row 를 $0$ ~ $M-1$ 회 회전시키는 것이 가능하다. 각 회전마다 $ k $ 만큼의 cost 가 추가로 소모된다.

 

풀이

오른쪽 혹은 아래 방향으로만 이동할 수 있으니 DP 문제이다. 

DP 배열은 $dp[i][j][s]$ 로 구성한다. 각각 현재 위치 $ (i, j) $, 현재 row 가 회전된 횟수 $ s $ 를 나타낸다.

DP 배열 시각화

 

오른쪽 이동에 의한 점화식은 다음과 같다.

$$ dp[i][j+1][s] \leftarrow dp[i][j][s] + cost[i][(s+j+1)\%M] $$

 

아래쪽 이동에 의한 점화식은 다음과 같이 구성할 수 있다.

현재 상태 $ (i, j, s_1) $ 에서 아래로 이동하기 전, 아래 row 를 임의의 횟수 $s_2 $ 만큼 회전하는 것이 가능하다.

따라서, $ s_1, s_2 \in [0, M-1] $ 에 대해 다음 점화식이 성립한다.

$$ dp[i+1][j][s_2] \leftarrow dp[i][j][s_1] + cost[i+1][(s_2+j+1)\%M] + k * s_2 $$

 

배열의 초기값은 모두 $inf$ 값으로 잡는다.

초기 좌표인 $(0,0)$ 에 대해서, 회전 cost 를 반영하여 다음과 같이 초기화한다.

$$ dp[0][0][s] \leftarrow cost[0][s] + k * s $$

 

코드 최적화

풀이를 실제로 구현하려 하면 몇 가지 제한에 부딪힌다.

 

첫 번째는 메모리 제한으로, $dp[i][j][s]$ ($i, j, s \leq 200$) 을 long long 으로 초기화하려 시도하면 segment fault 가 발생하는 것을 확인할 수 있다.

지나간 row 의 cost 값은 더 이상 참조할 필요가 없으므로 덮어씌워도 무방하다. 즉, 현재 row 와 아래 row 의 cost를 저장할 공간만 존재하면 되는 것이다.

 

이 발상을 통해 i 축의 크기를 2로 압축할 수 있다. $i = 0, 2, 4, ... $ 일시 $ i = 0 $ 의 공간을 활용하고, $i = 1, 3, 5, ... $ 일 시 $ i = 1 $ 의 공간을 활용한다.

이 때, 아래 row 의 cost값을 저장할 배열을 매번 $inf$ 로 초기화하는 것을 잊지 말아야 한다.

 

 

두 번째는 시간 제한이다. 

아래 row 를 $s_2$ 회 회전 후 아래로 이동하는 점화식을 모든 $ (i, j, s_1) $ 에 대해 계산하려면 시간복잡도가 $O(NM^3)$ 이 된다.

$$ dp[i+1][j][s_2] \leftarrow dp[i][j][s_1] + cost[i+1][(s_2+j+1)\%M] + k * s_2 $$

 

DP 특성상, 최종값은 무조건 최소값만 들어가게 된다.

$ s_1$ 와 $ s_2 $ 는 독립이므로, 현재 위치 $(i, j)$ 에서 cost가 가장 최소가 되는 $ s_1 $ 값에 대해서만 점화식을 계산해도 된다.

$$  dp[i+1][j][s_2] \leftarrow min_{(0 \leq s_1 < M)}(dp[i][j][s_1]) + cost[i+1][(s_2+j+1)\%M ] + k * s_2 $$

 

코드

더보기 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <climits>
using namespace std;

#define ll long long


void test() {
    int N, M;
    ll ENERGY;
    cin >> N >> M >> ENERGY;

    ll arr[201][201];
    ll dp[2][201][201];     // i%2, j, s
    ll ans = LLONG_MAX;

    // input
    for (int i=0;i<N;i++) {
        for (int j=0;j<M;j++) {
            cin >> arr[i][j];
        }
    }

    // initialize dp
    for (int k=0;k<2;k++) {
        for (int j=0;j<M;j++) {
            for (int s=0;s<M;s++) {
                dp[k][j][s] = LLONG_MAX;
            }
        }
    }

    for (int s=0;s<M;s++)
        dp[0][0][s] = ENERGY * s + arr[0][s];

    // dp
    #define MINDEF(x, y) x = min(x, y);
    for (int i=0;i<N;i++) {
        int k = i%2;

        for (int j=0;j<M;j++) {
            for (int s=0;s<M;s++) {
                dp[!k][j][s] = LLONG_MAX;
            }
        }

        for (int j=0;j<M;j++) {
            ll min_s = LLONG_MAX;

            for (int s=0;s<M;s++) {
                if (j < M-1)            
                    // horizontal
                    MINDEF(dp[k][j+1][s], dp[k][j][s] + arr[i][(s+j+1)%M])
                
                MINDEF(min_s, dp[k][j][s])
            }
            if (i == N-1)
                continue;

            for (int s2=0;s2<M;s2++)  
                // shift & vertical  
                MINDEF(dp[!k][j][s2], s2 * ENERGY + min_s + arr[i+1][(s2+j)%M])
        }
    }

    
    for (int s=0;s<M;s++)
        MINDEF(ans, dp[(N-1)%2][M-1][s])
    
    cout << ans << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int T;
    cin >> T;
    while (T--) test();
}

 

소감

문제 이해 및 점화식 떠올리기는 간단한데, 시간/메모리 제한에 맞게 구현하는 방법을 떠올리는 것이 조금 어려웠다. 그래도 공식 tutorial 을 확인하지 않고 풀어서 뿌듯하다.