취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 27532번 문제인 시계 맞추기이다.
문제는 아래 링크를 확인하자.

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

먼저, 가능한 모든 R값은 mod 720에 대하여 720가지뿐임을 관찰하자. 이 각각의 R에 대해 시각이 주어진 것과 같이 나타나려면 시계가 몇 개인지 구하고 문제를 해결하자.

고정한 각 R값에 대하여 각 시계의 시각을 "시계를 처음 건 시점"을 기준으로 저장한다면 크기 720의 배열에 모든 시계를 간단히 저장할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int N;
int arr[1500];
int ans = 1000000007;
int visited[720];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		string s; cin >> s;
		arr[i] = (stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 2))) % 720;
	}

	for (int R = 0; R < 720; R++) {
		memset(visited, 0, sizeof(visited));
		int cnt = 0;

		for (int i = 0; i < N; i++) {
			int t = arr[i] - (R * i) % 720;
			if (t < 0) t += 720;
			if (!visited[t]) visited[t] = 1, cnt++;
		}
		ans = min(ans, cnt);
	}

	cout << ans;
}