취미로 코딩하기

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

이번에 볼 문제는 백준 3554번 문제인 Enigmatic Device이다.
문제는 아래 링크를 확인하자.

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

이 문제가 출제된 때에는 naive한 구현으로 풀 수 없었을지 모르지만, 10년이 넘은 지금은 naive한 구현으로도 충분히 3초 내에 주어진 연산을 완료해낼 수 있다.

어떤 수 n을 (n*n)%2010으로 만드는 변환을 하나의 수에 반복적으로 적용하면 짧은 주기로 같은 수가 반복된다는 점을 이용하면 더 나은 시간복잡도로도 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N, Q;
int arr[50001];

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

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];

	cin >> Q;
	while (Q--) {
		int q, l, r; cin >> q >> l >> r;
		if (q == 2) {
			int ans = 0;
			for (int i = l; i <= r; i++) ans += arr[i];
			cout << ans << '\n';
		}
		else {
			for (int i = l; i <= r; i++) {
				arr[i] = (arr[i] * arr[i]) % 2010;
			}
		}
	}
}