[백준 19846번] 신기한 연산 (C++)

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

constructive 문제에 익숙하지 않으면 숨이 턱 막히는 문제일 수 있다.

constructive는 문제를 한 발짝 뒤에서 바라볼 수 있어야 한다.

 

이번 문제는 각 구간에 대해 홀수번 나오는 문자가 단 한 개인 예시를 만드는 문제이다.

구간도 여러개이고, 어떤 구간이 테스트 케이스로 주어질지 모르는데 그리디처럼 접근하면 코드가 매우 길어지고

난이도도 많이 올라간다.

 

Greedy 사고: 주어진 입력을 잘 활용하여 최적의 솔루션을 찾는 것

즉, 예시로부터 귀납적으로 생각해서 일반화하는 느낌

Constructive 사고: 입력과 같은 특정 구간이 아니라 어떠한 구간이 입력으로 주어지더라도 가능한 경우를 생각하는 것

즉, 문제 전체를 아우르는(?) 답을 생각해보고 예시가 맞는지 확인하는 느낌(나무가 아니라 숲을 보는 느낌)

 

입력 조건을 보면 각 구간의 너비는 2N-1 이상의 홀수라고 명시되어 있다.

예시를 통해 하나씩 가능하게 만드는 문자열을 만들어서 일반화하는 것이 아니라

어떻게 하면 항상 2N-1이상의 홀수 구간에서 항상 문제의 조건을 만족하는 문자열이 없을까? 식으로 접근해야 한다.

 

위와 같이 생각하다보면 문자열을 2개씩 연달아서 사용하면 된다는 생각을 하게 된다.

N=1일때 구간의 최소 길이 1(a)

N=2일때 구간의 최소 길이 3(aab)

N=3일때 구간의 최소 길이 5(aabbc)

...

2개씩 문자를 사용하면 문제의 조건을 모두 만족시킬 수 있다.

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n, m, q, s, e, tmp = 97;
	vector<char> c;
	cin >> n >> m >> q;
	for(int i = 0; i < q; i++){
		cin >> s >> e;
	}
	while(true){
		c.push_back(tmp);
		m--;
		if(!m) break;
		else{
			c.push_back(tmp);
			m--;
			if(!m) break;
			tmp = 97 + ((tmp-97+1)%n);
		}
	}
	for(auto v : c) cout << char(v);
}