[C++] 백준 10266 시계 사진들

문제 링크

---

www.acmicpc.net/problem/10266

10266번: 시계 사진들

접근 방법

---

 

 문제에서 2개의 시계가 주어진다. 정답을 찾기위해 우리는 시계2를 적절히 회전하여 시계1과 일치하는지 확인을 해야한다. 이것을 어떻게 풀어 갈 수 있을까? 

시계는 36만의 각도가 존재하므로 36만개의 문자열로 생각해보자. 이 때 시침이 가리키는 각도는 1, 아니면 0이라고 표기를 하자.

예를 들어 총 5개의 각도가 존재하고 ,각도1, 각도3을 시침이 가리킨다면

1

0

1

0

0

이러한 모양일 것이다. 

 

그럼 시계2를 회전 시켜 시계 1과 일치하게 하는 것은 어떻게 해야할까? 아래 그림을 보자!

시계 2를 회전 시킨다는 것은 위의 그림과 같이 시계를 오른쪽으로 이동시키는 과정이다. 또한 시계라는 특성상 끝 지점을 지나면 다시 처음으로 순환되는 구조이므로 시계1 두개를 이어 붙여버리면 순환구조를 탐색하는데 전혀 문제가 없게된다. 

 KMP알고리즘을 공부했다면 시계1을 두 개 이어붙인 것을 전체 TEXT, 시계2를 Pattern으로 사용하여 해결할 수 있을 것이다. KMP알고리즘을 잘 모른다면 countrysides.tistory.com/27를 참고하도록 하자.   

소스코드

---

#include <iostream>
#include <vector>
#include <string>
#define MAX 360000

using namespace std;

vector<int> getpi(vector<bool> pattern) {

	vector<int> pi(pattern.size(), 0);
	int j = 0;

	for (int i = 1; i < pattern.size(); i++) {
		while (j > 0 && pattern[i] != pattern[j]) {
			j = pi[j - 1];
		}
		if (pattern[i] == pattern[j]) {
			pi[i] = ++j;
		}
	}
	return pi;
}

string kmp(vector<bool> text, vector<bool> pattern) {

	vector<int> pi = getpi(pattern);
	int j = 0;

	for (int i = 0; i < text.size(); i++) {
		while (j > 0 && text[i] != pattern[j]) {
			j = pi[j - 1];
		}
		if (text[i] == pattern[j]) {
			if (j == pattern.size() - 1) {
				return "possible\n";
			}
			else
				j++;
		}
	}
	return "impossible\n";
}

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

	int n;
	vector<bool> clock1(MAX * 2, 0); // text
	vector<bool> clock2(MAX, 0);     // pattern

	cin >> n;

	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		clock1[num] = clock1[MAX+num] = 1;
	}
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		clock2[num] = 1;
	}

	cout << kmp(clock1, clock2);
}

개발 환경 : Visual Studio 2019

질문, 덧글, 지적 환영합니다.