Boj 2478) 자물쇠

문제

백준 2478

설명

왼쪽으로 a 칸 밀고, [b, c] 구간을 뒤집고, 다시 왼쪽으로 d 칸 미는 동작을 반복했을 때의 결과가 주어져있다. 어떻게 미지수를 구할까?

[b, c] 의 길이는 주어진 순열의 내림차순인 구간의 길이가 된다.

그리고 조금만 생각해보면 [b, c] 만 결정되면 a 와 d 는 바로 결정됨을 알 수 있다.

불가능한 경우는 없으므로 b 가 0 인 경우부터 하나씩 증가시키면서 셈하면 답을 구할 수 있을 것이다.

거기에 불가능한 경우인 a 를 0 으로 만드는 [b, c] 는 하나 뿐이고 d 에 대해서도 역시 마찬가지이다.

그러므로 최대 두번의 탐색으로 불가능한 경우를 제외시키고 답을 얻을 수 있다.

시간 복잡도

O(\(\mathrm{N}\))

코드

int main()
{
	vector<int> arr;
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr.emplace_back();
		arr[i]--; // mod 는 0 부터 시작하는게 계산이 편함
	}

	vector<int> s, e;
	for (int i = 0; i < n; i++)
	{
		int dff1 = (arr[(i + 1 + n) % n] - arr[i] + n) % n;
		int dff2 = (arr[i] - arr[(i - 1 + n) % n] + n) % n;
		if (dff1 != dff2)
		{
			if (dff1 == n - 1)  // 내림차순 시작
				s.push_back(i);
			else if (dff1 == 1) // 내림차순 끝
				e.push_back(i - 1);
		}
	}

	int ans[4];
	ans[3] = s.size() == 2 ? n - s[1] : s.size() == 1 ? n - s[0] : 1;
	ans[2] = s.size() == 2 ? e[0] - s[1] : s.size() == 1 ? e[0] - s[0] : n - 1;
	ans[2] = (ans[2] + n) % n;
	ans[1] = 0;

	int i_zero = find(arr.begin(), arr.end(), 0) - arr.begin();
	i_zero = (i_zero + ans[3]) % n;
	if(i_zero <= ans[2]) i_zero = ans[2] - i_zero;
	while (ans[3] == 0 || i_zero == 0)
	{
		ans[3] = (ans[3] + n - 1) % n;
		ans[2] = (ans[2] + n - 1) % n;
		ans[1] = (ans[1] + n - 1) % n;
		i_zero += 1;
	}
	ans[0] = (n - i_zero) % n;

	cout << ans[0] << endl;
	cout << ans[1] + 1 << ' ' << ans[2] + 1 << endl;
	cout << ans[3] << endl;
}