JOISC19 Lamps

문제

oj.uz/problem/view/JOI19_lamps

문제 보기 - Lamps (JOI19_lamps) :: oj.uz

N개의 램프가 꺼져 있거나 켜져 있을 때,

1. 구간을 정해 구간의 램프들을 모두 끈다.

2. 구간을 정해 구간의 램프들을 모두 켠다.

3. 구간을 정해 구간의 램프들을 모두 토글(뒤집는다)한다.

의 3가지 연산을 적용하여 A 상태의 램프들을 B 상태로 만들어야 할 때 연산의 최소 횟수를 구해야 한다.

$N<=1000000$

 

풀이

먼저, 연산의 순서를 적당히 바꿔 풀기 쉽도록 바꾸자.

Observation 1 : 모든 toggle 연산은 on/off 연산 다음에 위치할 수 있다.

만약 toggle 연산 뒤에 on/off 연산이 있을 때, 이 둘의 순서를 뒤바꿀 수 있음을 보이자.

만약 toggle 연산의 범위 안에 on/off 연산의 구간이 완벽히 포함되는 경우가 아니라면 on/off 연산은 그대로 두고, toggle 연산의 범위를 on/off 구간과 겹치지 않는 구간만 뽑아오면 된다.

toggle 연산의 범위 안에 on/off 연산의 범위가 완벽히 포함되면, on/off를 뒤집어 실행하고 그 뒤에 toggle 해주면 된다.

 

toggle 연산을 하기 전에는 on/off 연산만을 할 수 있다. 만약 on/off 연산을 모두 적용했을 때 배열의 업데이트 상태를 0으로 칠해진 적이 있으면 A, 1로 칠해진 적이 있으면 B, 그 아무 색으로도 칠해진 적이 없다면 C로 결정되어 있다고 생각하자.

C단위로 구간을 모두 자르고, 연속으로 같은 문자가 있다면 압축할 수 있으니 ABABAB의 꼴이 된다.

 

Observation 2 : on/off 연산이 서로 겹치지 않는 최적해가 존재한다.

인접한 두 on/off 연산이 하나가 완전히 포함되지 않고 겹친다면 Observation 1과 같이 하나를 잘라 주면 된다.

하나가 완벽히 포함된다면 포함되는 나중에 나오는 연산을 toggle 연산으로 치환해줄 수 있다.

 

따라서 ABABABCCABABCCABAB 꼴의 연산 비용은 단순히 A, B의 경계로, AB가 바뀌는 위치의 개수와 같다.

ABC가 정해진다면 결국 토글을 각 칸에 홀수번 적용해야 할지, 짝수번 정해져야 할지 알려주는 010101010의 문자열도 정해지게 된다.

01010101 문자열에서의 최적해는 단순히 서로 다른 1의 겹치지 않는 구간에 한번씩 토글 연산을 실행해주면 된다.

 

결국, ABC문자열만 정한다면 최적의 연산의 횟수가 결정되니, dp를 하며 ABC문자열만 정해주면 된다.

문자의 종류가 바뀌는 위치를 알아야 하니, 현재 구간에서의 마지막 칸의 문자의 종류를 기억하며 dp를 한다.

 

시간 복잡도 : $O(N)$

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 1e6;
 
int N, A[MAXN+10], B[MAXN+10];
int dp[MAXN+10][3];
 
int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%1d", &A[i]);
	for(int i=1; i<=N; i++) scanf("%1d", &B[i]);
 
	dp[1][0]=1+((0^B[1])==1);
	dp[1][1]=1+((1^B[1])==1);
	dp[1][2]=((A[1]^B[1])==1);
	for(int i=2; i<=N; i++)
	{
		dp[i][0]=dp[i][1]=dp[i][2]=987654321;
 
		dp[i][0]=min(dp[i][0], dp[i-1][0]+((0^B[i])==1 && (0^B[i-1])==0));
		dp[i][0]=min(dp[i][0], dp[i-1][1]+((0^B[i])==1 && (1^B[i-1])==0)+1);
		dp[i][0]=min(dp[i][0], dp[i-1][2]+((0^B[i])==1 && (A[i-1]^B[i-1])==0)+1);
		
		dp[i][1]=min(dp[i][1], dp[i-1][0]+((1^B[i])==1 && (0^B[i-1])==0)+1);
		dp[i][1]=min(dp[i][1], dp[i-1][1]+((1^B[i])==1 && (1^B[i-1])==0));
		dp[i][1]=min(dp[i][1], dp[i-1][2]+((1^B[i])==1 && (A[i-1]^B[i-1])==0)+1);
 
		dp[i][2]=min(dp[i][2], dp[i-1][0]+((A[i]^B[i])==1 && (0^B[i-1])==0));
		dp[i][2]=min(dp[i][2], dp[i-1][1]+((A[i]^B[i])==1 && (1^B[i-1])==0));
		dp[i][2]=min(dp[i][2], dp[i-1][2]+((A[i]^B[i])==1 && (A[i-1]^B[i-1])==0));
	}
	printf("%d\n", min({dp[N][0], dp[N][1], dp[N][2]}));
}