Problem Solving Diary #29

JOISC 문제 몇 개를 땅따먹기에서 풀어 보았다.

 

BOJ 24137. 塗り箸 (Chopsticks)

옛날 NYPC의 어떤 output only와 상당히 비슷해 보이는 문제이다.

 

형태를 봤을 때 구간 DP로 진행하는 것이 가장 좋아 보인다. 어떤 구간 $[l, r]$에 대해 최소 비용으로 칠하는 방법을 구한다고 생각해 보자. 먼저 이 구간 전체에 색칠할 색 $c$를 정한다. 다음으로 이 위에 덮어쓸 구간을 정한다. 모든 $c$에 대한 최소 비용을 $[l, r]$에 대한 최소 비용으로 정한다. 이렇게 하면 $O(N^3)$ 풀이가 나온다. 상수가 $52/6$ 정도로 다소 커서 걱정되지만, 짜 보면 문제없이 통과된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int arr[302];
int cnt[302][52];
int DP[302][302];
int minC[52][302];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        char c;
        scanf(" %c", &c);
        arr[i] = islower(c) ? (c-'a') : (c-'A'+26);

        for(int z=0; z<52; z++) cnt[i][z] = cnt[i-1][z] + (arr[i] == z);
    }

    for(int l=n; l>=1; l--){
        for(int c=0; c<52; c++) for(int i=l; i<=n; i++) minC[c][i] = 1e9;
        for(int c=0; c<52; c++){
            minC[c][l] = (c==arr[l] ? 1 : 2);
            for(int r=l+1; r<=n; r++){
                if(arr[r] == c) minC[c][r] = minC[c][r-1];
                else minC[c][r] = minC[c][r-1] + 1;
                for(int prv=r; prv>l; prv--){
                    minC[c][r] = min(minC[c][r], minC[c][prv-1] + DP[prv][r]);
                }
            }
        }
        for(int i=l; i<=n; i++) DP[l][i] = 1e9;
        for(int c=0; c<52; c++) for(int i=l; i<=n; i++) DP[l][i] = min(DP[l][i], minC[c][i]);
    }

    printf("%d", DP[1][n]);
}

 

BOJ 24128. 判子 (はんこ) (Stamp)

문제에서는 최소 횟수의 연산, 그리고 그때의 최소 시작 길이를 구하는 게 목표이다. 따라서 연산을 증가시키지 않으면서 시작 길이를 줄이는 몇 가지 방법들을 살펴보자.

 

만약 최초 문자열 $S$에서 연속한 두 문자가 삭제되었다고 생각해 보자. 그렇다면 이 두 문자는 애초에 안 만들었어도 됐다. 그렇기에 이러한 케이스는 빼고 생각해도 된다. 마찬가지로, 최초 문자열 $S$에서 연속한 두 문자가 변경되었다면 이 두 문자는 그냥 안 만들고 두 개를 삽입하는 게 이득이다. 따라서 이런 경우도 없다.

 

최초 문자열 $S$에서 한 문자가 삭제되었다고 생각해 보자. 이 경우 예를 들어,

• 원본 문자열: IOIOIOI
• 나중 문자열: IOIIOI

와 같이 바뀔 수 있다. 그런데 이것은 IOIOI에서 I를 추가해 만들 수도 있다. 따라서, 한 문자를 삭제하는 것이 항상 손해라는 추측을 할 수 있다. 조금 더 엄밀한 증명은 다음과 같다.

• 증명: O를 삭제하는 것이 최적이라고 가정하자. 그러면 이 전에서 관찰한 성질에 따라 양옆의 I는 삭제하지 않아야 할 것이다. 이 세 글자가 각각 $k$, $k+1$, $k+2$번째 글자라고 하자. O를 삭제한 뒤 만약 $k$번 글자와 $k+2$번 글자 사이에 삽입한 글자 중 O가 하나라도 있다면, 당연히 이걸 새로 삽입하지 말고 애초에 O를 남겨두는 것이 최적이다. 그렇지 않다면, $k$번 글자와 $k+2$번 글자 사이에 삽입한 글자는 모두 I일 것이다. 그런데 이 I들은 $k+2$번째 글자 뒤에 삽입해도 아무런 상관이 없다. 따라서, 애초에 OI를 하나 덜 만들고 I를 하나 더 삽입한다고 생각하면 연산 횟수는 그대로고 최초 문자열 길이는 더 짧아진다. 따라서, O를 삭제하는 것은 항상 최적이 아니다.
• I를 삭제하는 경우에도, 대부분의 경우 위 논리가 그대로 적용이 가능하다. 예외가 되는 케이스는 맨 처음이나 맨 마지막 I를 삭제하는 경우이다. 만약 맨 마지막 I인 경우, 그냥 마지막 OI를 하나 덜 만들고 O를 추가하는 게 비슷한 이유로 이득이다. 맨 앞의 경우에도 반대로 생각할 수 있다. 이렇게 하고 나면 결국 최초 문자열이 I 한 글자인 경우를 제외하고는 항상 손해라는 결과가 나온다.
• 최초 문자열이 I인 경우에, 해당 글자를 삭제하는 게 이득이려면 문자열 전체가 O로 이루어져 있어야 한다. 그런데 O가 $1$개 이상이라면 I를 삭제하느니 O로 변경하는게 무조건 이득이다. $S$가 빈 문자열일 경우는 없으므로, 문자를 삭제하는 것은 항상 최적이 아니다.

따라서 우리는 문자를 변경하는 경우와 삽입하는 경우만 봐도 충분하다. 이건 DP를 통해 처리할 수 있다. $S$의 각 글자에 IOIO…I의 각 문자를 대응시킨다고 생각하자. 물론 삽입인 경우에는 대응이 안 될 수도 있다. 현재까지 대응시킨 글자의 홀짝성에 따라 경우를 나눠 처리한다. $DP[x][d]$는 현재 $S$의 $x$번째 문자까지 IOIOI 문자열의 문자 대응 수 홀짝성이 $d$일 때, (최소 연산 수, 최소 최초 길이)를 DP로 전이하면 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 1e9;

struct dat{
    int turn, len;
    dat(){}
    dat(int turn, int len): turn(turn), len(len){}

    bool operator<(const dat &r)const{
        if(turn != r.turn) return turn < r.turn;
        return len < r.len;
    }

    dat operator+(const dat r)const{
        return dat(turn+r.turn, len+r.len);
    }
};

int n;
bool arr[1000005];
dat DP[1000005][2];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        char c;
        scanf(" %c", &c);
        arr[i] = (c=='I');
    }

    for(int i=0; i<=n; i++) DP[i][0] = DP[i][1] = dat(INF, INF);
    DP[0][0] = dat(0, 0);
    for(int i=1; i<=n; i++){
        if(arr[i] == 1){
            DP[i][0] = min(DP[i-1][0] + dat(1, 0), DP[i-1][1] + dat(1, 1));
            DP[i][1] = min(DP[i-1][1] + dat(1, 0), DP[i-1][0] + dat(0, 1));
        }
        else{
            DP[i][0] = min(DP[i-1][0] + dat(1, 0), DP[i-1][1] + dat(0, 1));
            DP[i][1] = min(DP[i-1][1] + dat(1, 0), DP[i-1][0] + dat(1, 1));
        }
    }

    printf("%d\n%d", DP[n][1].turn, DP[n][1].len);
}

 

BOJ 17735. Collecting Stamps

최적해의 형태를 생각해보면, 다음과 같은 형태이다.

• $A_1 = 0$번 역에서 시작해 상행선을 탄다.
• $B_1$번 역에서 내린 뒤, 하행선을 타고 $A_2$번 역으로 간다.
• $A_2$번 역에서 상행선을 탄 뒤, $B_2$번 역에서 내린다.
• $\cdots$
• $A_k$번 역에서 상행선을 탄 뒤, $B_k = N+1$번 역에서 상행선을 내려 종료한다.

이 도중에 언제든 스탬프를 위해 내렸다가 다시 타던 열차를 탈 수 있다고 가정한다. 위 정의상 당연히 $A_i < B_i$, $A_{i+1} < B_i$여야 한다.

 

하행선을 타는 이유는 다음 두 가지로 생각해볼 수 있다.

• 상행선을 타다 $i$번 역에 내려 스탬프를 찍고 다시 상행선을 타는 게 너무 비싸다. 이럴 경우 $i$번 역에서 하행선으로 갈아탄다.
• 또는 아예 하행선을 타다 $i$번 역에 내리고 하행선을 계속 타거나 상행선으로 갈아탈 수도 있다.

이유야 어찌됐든, 역들을 다음과 같이 네 가지로 분류할 수 있다.

• 상행선에서 하행선으로 갈아타는 역
• 하행선에서 상행선으로 갈아타는 역
• 환승이 일어나지 않는 대신, 상행선과 하행선 둘 모두로 지나가는 역
• 환승이 없고, 상행선으로만 지나가는 역

여기서 우리는 환승 cost를 생각해볼 수 있다. 환승은 어떤 역 $x$에서 상행선을 타다 하행선으로 가기 위해 발생하는 비용, 또는 그 반대의 비용을 말한다. 이 경우 환승을 언제 할지 정한다면 cost 계산은 쉽다. 그러나 환승이 일어나지 않는 역의 경우 상행선을 타던 중, 또는 하행선을 타던 중에 스탬프를 받으러 와야 한다. 이때 additional cost가 생긴다. 상행선과 하행선으로 둘 다 지나가는 역의 경우 양쪽 방법 중 min을 택할 수 있고, 그렇지 않은 경우 무조건 상행선 cost로 계산해야 한다.

 

이 구조에서 DP를 생각해볼 수 있다. 아래 관찰이 있어야만 DP를 할 수 있는 건 아니지만, DP를 조금 더 편하게 해 줄 이 관찰을 보자.

• 어떤 역 $x$에서 상행->하행 환승, 하행->상행 환승을 둘 다 할 일은 없다.
• 증명: 만약 저런 최적해가 있으면, 환승을 안 하는 게 이득임을 알 수 있다.

따라서, 각 역에서 일어나는 일은 상행->하행 환승, 하행->상행 환승 두 가지뿐임을 알 수 있다. 물론 한 역에서 여러 차례 상행->하행 환승을 하는 것도 가능하고, 반대편 환승도 여러 번 하는 게 가능하다.

 

여기서 $DP[x][y]$를 다음과 같이 정의하자.

• $DP[x][y]$: $1$번부터 $x$번 역까지 (하행->상행 환승 횟수) - (상행->하행 환승 횟수)가 $y$인 경우, $y$번 역까지의 스탬프를 모두 얻는 최소 비용

$y \le n$인 경우만 생각해도 충분하다. 저 DP를 그냥 전이하면 $O(n^3)$에 문제를 해결할 수 있다. 이렇게만 해도 85점이 나오는데, 아무래도 여기까지의 관찰이 핵심적이라 그런 것 같다.

 

$O(n^2)$ 정도의 시간 복잡도로 줄이기 위해 DP 점화식을 써 보면,

• $DP[x-1][y] \rightarrow DP[x][y+k]$: 비용 $(2y+1)t+k(D_x + V_x)$ 추가
• $DP[x-1][y] \rightarrow DP[x][y-k]$: 비용 $(2y+1)t+k(U_x + E_x)$ 추가
• $DP[x-1][y] \rightarrow DP[x][y]$: $y \neq 0$인 경우 $(2y+1)t+\min(U_i + V_i, E_i + D_i)$ 추가, $y = 0$인 경우 $t+U_i + V_i$ 추가

세 번째는 naive하게 해도 $O(n^2)$이다. 위 두 가지도 어렵지 않게 $O(n^2)$으로 줄일 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

int n; ll T;
ll U[3002], V[3002], D[3002], E[3002];
ll DP[3002][3002];

int main(){
    scanf("%d %lld", &n, &T);
    for(int i=1; i<=n; i++) scanf("%lld %lld %lld %lld", &U[i], &V[i], &D[i], &E[i]);

    for(int i=0; i<=n+1; i++) for(int j=0; j<=n+1; j++) DP[i][j] = INF;
    DP[0][0] = 0;
    for(int i=1; i<=n; i++){
        DP[i][0] = DP[i-1][0] + T + U[i] + V[i];
        for(int j=1; j<=n; j++) DP[i][j] = DP[i-1][j] + (2*j+1)*T + min(U[i]+V[i], D[i]+E[i]);

        ll old = DP[i-1][0] + T + D[i] + V[i];
        for(int j=1; j<=n; j++){
            DP[i][j] = min(DP[i][j], old);
            old = min(old, DP[i-1][j] + (j*2+1)*T) + D[i] + V[i];
        }

        old = DP[i-1][n] + (2*n+1)*T + U[i] + E[i];
        for(int j=n-1; j>=0; j--){
            DP[i][j] = min(DP[i][j], old);
            old = min(old, DP[i-1][j] + (j*2+1)*T) + U[i] + E[i];
        }
    }

    printf("%lld", DP[n][0] + T);
}