[boj : 19846] 신기한 연산

www.acmicpc.net/problem/19846

19846번: 신기한 연산

문제 : 재현이가 원하는 조건에 맞는 문자열을 구해라. 주어진 구간은 항상 홀수개의 알파벳은 하나, 나머지는 전부 짝수이다.

 

해설 :

djm03178님께 먼저 감사함을 표합니다.(팬이에요ㅎㅎ)

너무 너무 어렵게 풀었다,,,,적어도 나한테는 ㅠㅠㅠ 

먼저 정말 단순하게 생각을 해보자.

문자열을 미리 aaaaaaa~ 로 배치해 놓고 주어지는 구간에 맞추어 하나씩 바꾸면서 조절해 주면서 답을 구하면 된다.

그러나 문자열의 길이는 100000 이고 주어지는 구간의 수는 100000 이다.

제한시간인 1초를 감당을 할 수가 없게 된다.

 

자,그러면 생각을 바꾸어보자. 매번 주어지는 구간마다 문자열을 바꾸는 것이 아닌 '먼저 문자열을 주어진 조건에 맞게 정해주게 된다면?' 주어지는 구간에 상관없이 무조건적으로 조건에 맞는 답이 되겠죠.

즉, 주어지는 구간을 배제한체로 모든 구간에 관해 

 

'부분 문자열을 뽑았을 때, 각 부분 문자열에는 N종류의 알파벳이 전부 등장하며 그중 홀수 번 등장하는 알파벳이 단 한 종류 있음이 보장된다.'

 

라는 조건에 맞는 문자열을 한번 구해보도록 합시다.

 

주어지는 구간의 길이는 항상 '홀수'입니다. 이는 괜히 주어진 조건이 아니겠죠.

기준이 되는 구간을 우리가 정했다고 가정해봅시다. 그럼 이 구간에 대해 늘리거나 줄이게 된다면 그만큼 홀수/짝수의 알파벳이 달라지게 됩니다. 이를 동시에 매꿀수 있도록 만들어준다면 우리가 원하는 답을 구할 수가 있습니다.

 

그럼 항상 '홀수'의 구간만을 잡으면 되니 알파벳을 차례대로 2개씩 배치시켜 늘려준다면 이 문자열에서 어떤 구간을 잡아도 결국 항상 '홀수'개의 알파벳은 존재할 수 밖에 없게 되는 것이죠.

 

ex) n=3 m=10 

aabbccaabb

여기서 아무런 구간을 잡아도 항상 (짝수-1)이니 홀수개의 알파벳은 존재합니다.

 

#include<bits/stdc++.h>

using namespace std;

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

	int n, m, q;
	string s="";
	cin >> n >> m >> q;
	
	int cnt = 0;
	for (int i = 0; i < m; i++) {
		s += ('a' + cnt);
		if (i & 1)
			cnt = (cnt + 1) % n;
	}
	int x, y;
	for (int i = 0; i < q; i++)
		cin >> x >> y;
	cout << s;
	return 0;
}