백준17675 램프

작성일 | In

문제 링크

  • https://icpc.me/17675

문제 출처

  • 2018/2019 JOISC Day3 2번

사용 알고리즘

  • DP

시간복잡도

  • $O(N)$

풀이

기본적인 관찰이 몇 가지 필요합니다.

  • 한 지점에 1번 연산과 2번 연산을 모두 사용할 필요 없음
  • 한 지점에 3번 연산을 여러 번 사용할 필요 없음
  • 3번 연산은 1, 2번 연산을 모두 끝낸 다음에 해도 됨
  • 1, 2번 연산을 적용하는 구간은 서로 겹치지 않음
  • 3번 연산을 적용하는 구간은 서로 겹치지 않음

조금 더 생각해 보면, 1번 연산을 사용한 구간과 2번 연산을 사용한 구간이 인접하지 않는 최적해가 항상 존재함을 알 수 있습니다. 만약 두 구간이 인접하는 최적해가 존재한다면, 두 구간의 합집합에 1번 연산을 적용한 다음 2번 연산을 사용할 구간에 3번 연산을 사용하면 되기 때문입니다.

이제, 최소 횟수로 램프를 조작하는 전략을 만들 것입니다. 1번 연산과 2번 연산을 이용해 수열에 0과 1을 적당히 배치한 다음 3번 연산을 적당히 적용할 것입니다. 1번 연산을 이용해 0으로 바꾼 위치를 0, 2번 연산을 이용해 1로 바꾼 위치를 1, 연산을 수행하지 않아서 값이 바뀌지 않은 위치를 x라고 표시합시다. 0과 1은 인접하지 않기 때문에 xx00xx00xx11xx00xx11 같은 꼴이 나올 것입니다.

점화식을 다음과 같이 정의합시다.

  • $D(i, j) := A[1\cdots i]$만 신경썼을 때, $i$번째 값에 $j$를 배치한 다음 $A[1\cdots i]$와 $B[1\cdots i]$를 동일하게 만들 때 필요한 연산의 최소 횟수
  • $C(i, j) := i$번째 값에 $j$를 배치했을 때 $B[i]$와 동이랗면 0, 다르면 1. 즉, 3번 연산의 필요 여부를 나타내는 배열

$C$ 배열을 이용하면 $D$ 배열을 쉽게 계산할 수 있습니다. 상태는 총 $3N$개 있고 각 상태의 답을 $O(1)$에 구할 수 있으므로 $O(N)$ 시간에 문제를 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int N, A[1010101], B[1010101], C[1010101][3], D[1010101][3];

int SetCost(int idx, int prv, int now){ return now != 2 && prv != now; }
int FlipCost(int idx, int prv, int now){ return C[idx-1][prv] == 0 && C[idx][now] == 1; }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++){ char c; cin >> c; A[i] = c - '0'; }
    for(int i=1; i<=N; i++){ char c; cin >> c; B[i] = c - '0'; }
    for(int i=1; i<=N; i++) C[i][0] = B[i] != 0, C[i][1] = B[i] != 1, C[i][2] = A[i] != B[i];

    memset(D, 0x3f, sizeof D);
    D[1][0] = 1 + C[1][0]; D[1][1] = 1 + C[1][1]; D[1][2] = C[1][2];
    for(int i=2; i<=N; i++){
        for(int now=0; now<3; now++) for(int prv=0; prv<3; prv++) D[i][now] = min(D[i][now], D[i-1][prv] + SetCost(i, prv, now) + FlipCost(i, prv, now));
    }
    cout << *min_element(D[N], D[N]+3);
}