백준 C++ | #8 BOJ3048 개미 C++ 문제 풀이

3048번: 개미 (acmicpc.net)

 

왼쪽에서 오른쪽으로 이동하는 개미 사이 사이에 오른쪽에서 왼쪽으로 이동하는 개미 그룹이 들어간다는 발상으로 풀었다. 

예를 들면, A B C 와 D E F가 만나는 상황에서 

_ A _ B _ C _ 네 개의 빈칸에 DEF가 들어간다. 

이 네 개의 빈칸을 벡터로 만들어 T초에 맞게 코드를 짰다. 

 

다 풀고나서 제출했더니 메모리 초과 문제가 발생하였다. 

알고보니 j=0으로 시작하는 for 문에서 j-1 indexing을 해서 생긴 문제였다.

j=1부터 시작하는 것으로 바꾸어서 해결했다. 

 

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

int main() {
	// 첫번째 그룹, 두번째 그룹의 사이즈
	int n1, n2;
	std::string ant1_tmp, ant2_tmp;
	std::cin >> n1 >> n2;
	// 첫번째 그룹 개미
	std::cin >> ant1_tmp;
	std::vector<char> list1(ant1_tmp.begin(), ant1_tmp.end());
	std:reverse(ant1_tmp.begin(), ant1_tmp.end());
	// 두번째 그룹 개미
	std::cin >> ant2_tmp;
	std::vector<char> list2(ant2_tmp.begin(), ant2_tmp.end());
	
	// t초 뒤
	int t;
	std::cin >> t;
	std::vector<int> beet(n1 + 1);
	beet[n1] = n2;
	
	for (int i = 0; i < t; i++) {
		// t초마다 도는 루프
		for (int j = 1; j < n1 + 1; j++) {
			if (beet[j] > 0) {
				beet[j] -= 1;
				beet[j - 1] += 1;
			}
		}
	}
	// t초 뒤 구성에 맞추어 출력
	int saveIndex = 0;
	for (int i = 0; i < beet[0]; i++) {
		std::cout << ant2_tmp[i];
	}
	saveIndex += beet[0];
	for (int i = 0; i < n1; i++) {
		std::cout << ant1_tmp[i];
		for (int j = 0; j < beet[i+1]; j++) {
			std::cout << ant2_tmp[saveIndex + j];
		}
		saveIndex += beet[i + 1];
	}
	
	return 0;
}