개미
문제 해석
서로 반대 방향으로 이동하는 두 개미 그룹이 T초가 지났을 때, 개미의 순서를 구하는 문제입니다.
1초마다 자신의 앞에 반대방향으로 움직이는 개미가 있으면 서로 건너 뜁니다.
설계(10)
단순 구현문제입니다.
범위가 적어 매 초마다O(T) 각 개미들의 상태를 체크(O(N+M)))해주면 됩니다.
그러나, 저는 매 초마다 시뮬레이션으로 진행하는 것처럼 구현하지 않고, 한번의 각 개미들의 상태만으로 구현할 수 있도록 최적화하였습니다.
우선, 각 개미들이 겹친 정도를 표현하기 위해서 arr배열을 사용합니다.
0초
...DEF
CBA...
1초
..DEF
CBA..
2초
.DEF
CBA.
3초
DEF
CBA
4초
DEF.
.CBA
...
위와 같은 방식으로 T초에 어떤 상태인지 예측하여, 위와 아래의 문자를 번갈아가며 출력하면 원하는 결과를 얻을 수 있습니다.
여기서 주의할 점은 그룹 2의 경우에는 인덱스 N에서 시작해서 max(0,N-t)를 만족해야합니다.
그룹 1의 경우는 t초의 시작 인덱스가 0보다 크거나 같고 min(-(N-t),M)을 만족해야합니다.
구현(20)
코드
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int N,M;
string A,B;
int t;
char arr[30][2];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
memset(arr,0,sizeof(arr));
cin >> N >> M >> A >> B >> t;
reverse(A.begin(),A.end());
int idx = min((int)B.size(),max(0,-((int)A.size()-t)));
for (int i =0; i< N; i++){
arr[idx++][1]= A[i];
}
idx= max(0,(int)A.size()-t);
for (int i=0;i<M;i++){
arr[idx++][0] = B[i];
}
for (int i= 0; i<30;i++){
if (!arr[i][0] && !arr[i][1]) break;
if(arr[i][0]) cout << arr[i][0];
if(arr[i][1]) cout << arr[i][1];
}
return 0;
}
디버깅
그룹 2가 N을 넘어서는 경우, 그룹 1의 시작인덱스가 변화되야하는 것을 캐치하지 못했습니다.
DEF...
...ABC
위와 같은 반례를 생각하지 못해서 다시 구현하였습니다.
제출결과
0 ms
마무리
단순 구현문제였습니다.
T초마다 일일히 체크하고싶지 않아서 한번에 구현가능하도록 하였습니다.