백준 BOJ 10266 - 시계 사진들

KMP 알고리즘을 장기기억에 남기기위해서 텀을 두고 풀고있다

아직까지는 기억해내는듯

 

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

10266번: 시계 사진들

시곗바늘의 위치가 36만 등분된 각도값으로 주어질 때,

시계 1번을 적절히 회전하여 시계 2번을 만들 수 있는지 묻는 문제이다.

 

시곗바늘의 위치를 36만칸 짜리 배열에다 저장해서, 시곗바늘이 있는 곳의 배열 값을 1이라고 했을때

배열을 주우우욱 나열해놓고 보면

0과 1로 만들어진 36만자 짜리 문자열이 된다.

 

그러면 문제가

"36만자 문자열 두개를 적절히 밀어서 같게 만들수 있는가?"

가 되고

 

시곗바늘은 원형으로 배치되어있기 때문에, 360도 이상 ( 한바퀴 이상 == 36만자 이상 )

회전하거나 미는것은 의미가 없다는것을 알아낼 수 있다.

 

따라서 문자열 A와 B가 있을때

A를 두개 이어붙인 A' 안에 B가 있는지를 확인하면 되는 KMP 구현 문제가 된다.

 

소스코드 열어보기

#include <bits/stdc++.h>
using namespace std;

int fail[360001] = {0};

char s1[720001] = {0};
char s2[360001] = {0};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N = 360000;
	int n,k;
	cin >> n;
	for(int i=0; i<n; i++){ cin >> k; s1[k] = 1; s1[k+360000] = 1;}
	for(int i=0; i<n; i++){ cin >> k; s2[k] = 1; }
	
	for(int i=0,j=1; j<N; j++){
		while(i>0 && s2[i] != s2[j]) i = fail[i-1];
		if(s2[i] == s2[j]) fail[j] = ++i;
	}
	
	for(int i=0,j=0; j<N*2; j++){
		while(i>0 && s2[i] != s1[j]) i = fail[i-1];
		if(s2[i] == s1[j]){
			if(i == N-1){
				cout << "possible";
				i = fail[i];
				return 0;
			}
			else i++;
		}
	}
	
	cout << "impossible";
	return 0;
}

 

아직 KMP 구현법을 까먹지 않았다는것을 확인(1)