[백준 3048] 개미

옛날에 문자열로만 해보려고 하다 못푼 문제다

 

단순화 해서 풀면 되는데

그냥 한 그룹 개미를 다 1로 보고

다른 그룹 개미는 다 0으로 보고 풀어주면 된다

 

어차피 나중에 출력할때는 그룹의 개미들 순서는 정해져있으므로 배치만 하면 되는 것이니까

배치가 어떻게 되는지만 구하면 된다

 

그리고 T가 50이하이기 때문에

시뮬레이션으로 돌려도 1초안에는 해결할 수 있다

즉 시간초과가 안난다

 

여기서 시간초과 안나는걸 짐작해볼 수 있는게

개미는 알파벳 대문자로만 구성되어 있고

개미들은 중복되지 않으므로

두 그룹의 개미를 연결한 문자열을 최대 26글자

 

이걸 2중포문으로 돌려도 50*26 == 1000 남짓이므로

충분히 1초안에 돌릴 수 있다

 

---

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

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

	int N1, N2,T;
	cin >> N1 >> N2;
	string s1; cin >> s1;
	reverse(s1.begin(), s1.end());
	string s2; cin >> s2;
	cin >> T;

	string str;
	for (int i = 0; i < N1; i++) str += "1";
	for (int i = 0; i < N2; i++) str += "0";

	for (int i = 0; i < T; i++) {
		for (int k = 0; k < str.size()-1; k++) {
			if (str[k]=='1' && str[k + 1] =='0') {
				str[k + 1] = '1';
				str[k] = '0';
				k++;
			}
		}
	}

	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '1') {
			str[i] = s1[0];
			s1 = s1.substr(1);
		}
		else {
			str[i] = s2[0];
			s2 = s2.substr(1);
		}
	}
	cout << str;
	return 0;
}

 

일단 손이 가는대로 했는데 솔떳다

근데 몇군데 다듬을 수 있을 듯 하다