5. 백준 C++[3048] 개미

[3048] 개미

---

 

난이도: Silver 4

시도횟수: 1

www.acmicpc.net/problem/3048

문제

개미가 일렬로 이동할 때, 가장 앞의 개미를 제외한 나머지 개미는 모두 앞에 개미가 한 마리씩 있다.

서로 반대 방향으로 이동하던 두 개미 그룹이 좁은 길에서 만났을 때, 개미는 어떻게 지나갈까?

최근 연구에 의하면 위와 같은 상황이 벌어지면 개미는 서로를 점프해서 넘어간다고 한다.

즉, 두 그룹이 만났을 때, 1초에 한번씩 개미는 서로를 뛰어 넘는다. (한 개미가 다른 개미를 뛰어 넘고, 다른 개미는 그냥 전진한다고 생각해도 된다)

하지만 모든 개미가 점프를 하는 것은 아니다. 자신의 앞에 반대 방향으로 움직이던 개미가 있는 경우에만 점프를 하게 된다.

첫 번째 그룹이 ABC로 움직이고, 두 번째 그룹의 개미가 DEF순으로 움직인다고 하자. 그럼, 좁은 길에서 만났을 때, 개미의 순서는 CBADEF가 된다. 1초가 지났을 때는 자신의 앞에 반대방향으로 움직이는 개미가 있는 개미는 A와 D다. 따라서, 개미의 순서는 CBDAEF가 된다. 2초가 되었을 때, 자신의 앞에 반대 방향으로 움직이는 개미는 B,D,A,E가 있다. 따라서, 개미의 순서는 CDBEAF가 된다.

T초가 지난 후에 개미의 순서를 구하는 프로그램을 작성하시오.

 

---

제출한 코드

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


int main() {
	int N1 = 0;
	int N2 = 0;
	int T;
	cin >> N1 >> N2;

	string right, left;
	cin >> right;
	cin >> left;
	cin >> T;
	reverse(right.begin(), right.end());
	string ant = right + left;
	int time = 0;
	while (time < T) {
		for (int i = 0; i < N1 + N2 - 1;i++) {
			if (right.find(ant[i]) != string::npos && left.find(ant[i + 1]) != string::npos) {
				swap(ant[i], ant[i + 1]);
				i++;
			}
		}
		time += 1;
	}
	cout << ant;
	
	return 0;
}

 

  string의 여러 method들을 복습하는 문제. STL도 복습이 되었다.

 

1. string도 algorithm의 reverse 이용 가능

2. string은 +, -의 연산 지원

3. string에 존재하는지 여부는 find 함수로 확인.

있다면 index를, 없다면 string::npos를 반환한다. (python에서는 in 으로 간단하게 됨)

4. swap도 algorithm을 이용

 

여기서는 오른쪽으로 향하는 개미를 reverse시키고, ant 문자열을 만든 뒤에 ant[i]와 ant[i+1]이 마주보고 있다면 둘을 swap해주고, i++를 해주었다. 이미 swap해준 개미 친구를 또 해주면 안되기 때문.

 

프방론 배운지 1달밖에 안됐는데 다시 까먹고 있다