약 10일 전 쯤 내가 풀었던 문제 같은데, 다시 보니까 못풀고 있어서, 여기에 다시 정리해보았다.

[시뮬레이션] 만나는 그 순간

💡 문제 이해

두 사람 A, B가 동일한 시작점에서 출발하여 각자의 이동 명령(L 또는 R)에 따라 1초에 1m씩 움직일 때, 최초로 만나는 시간을 구하는 문제입니다.

🤔 문제 해결 방향

  1. A와 B 각각의 매 초별 위치를 배열에 기록합니다.
  2. 시간을 1초부터 검사하면서, A와 B의 위치가 일치하는 최초의 시점을 찾습니다.

주의할 점

전체 이동 시간이 큰 배열을 필요로 할 수 있습니다. (MAX_T = 1000000) A와 B의 시작 위치는 0으로 초기화되어야 합니다. 만약 움직임이 끝날 때까지 만나지 않으면 -1을 출력해야 합니다.

✍️ 코드

내 코드

#include <iostream>
using namespace std;

#define MAX_T 1000000

int n, m;
int pos_a[MAX_T + 1], pos_b[MAX_T + 1];     // 1 based indexing
int total_t = 0;

int main() {
    // 시작 위치
    pos_a[0] = 0;
    pos_b[0] = 0;

    cin >> n >> m;

    // A의 이동 기록
    for(int i = 0; i < n; i++) {
        char d;
        int t;
        cin >> d >> t;

        for(int j = total_t + 1; j <= total_t + t; j++) {
            if(d == 'L') pos_a[j] = pos_a[j - 1] - 1;
            else if(d == 'R') pos_a[j] = pos_a[j - 1] + 1;
        }
        total_t += t;
    }
    total_t = 0;

    // B의 이동 기록
    for(int i = 0; i < m; i++) {
        char d;
        int t;
        cin >> d >> t;

        for(int j = total_t + 1; j <= total_t + t; j++) {
            if(d == 'L') pos_b[j] = pos_b[j - 1] - 1;
            else if(d == 'R') pos_b[j] = pos_b[j - 1] + 1;
        }
        total_t += t;
    }

    // 만나는 시점 찾기
    int ans = 0;
    for(int i = 1; i <= total_t; i++) {
        if(pos_a[i] == pos_b[i]) {
            ans = i;
            break;
        }
    }

    if(ans) cout << ans;
    else cout << -1;
    return 0;
}

해설 코드

#include <iostream>
#define MAX_T 1000000

using namespace std;

int n, m;
int pos_a[MAX_T + 1], pos_b[MAX_T + 1];

int main() {
    cin >> n >> m;

    // A의 이동 기록
    int time_a = 1;
    for(int i = 0; i < n; i++) {
        char d; int t;
        cin >> d >> t;

        while(t--) {
            pos_a[time_a] = pos_a[time_a - 1] + (d == 'R' ? 1 : -1);
            time_a++;
        }
    }

    // B의 이동 기록
    int time_b = 1;
    for(int i = 0; i < m; i++) {
        char d; int t;
        cin >> d >> t;

        while(t--) {
            pos_b[time_b] = pos_b[time_b - 1] + (d == 'R' ? 1 : -1);
            time_b++;
        }
    }

    // 최초로 만나는 시간 탐색
    int ans = -1;
    for(int i = 1; i < time_a; i++) {
        if(pos_a[i] == pos_b[i]) {
            ans = i;
            break;
        }
    }

    cout << ans;
    return 0;
}

🔎 코드 비교 분석

두 코드는 동일한 아이디어로 구현되었으나, 몇 가지 구현 방식의 차이가 있습니다:

  1. 시간 관리 방식

    • 내 코드: total_t 변수로 누적 시간 관리
    • 해설 코드: time_a, time_b 변수로 개별 시간 관리

  2. 반복문 구조

    • 내 코드: for문으로 시간 범위 지정
    • 해설 코드: while(t--)로 카운트다운 방식

  3. 방향 처리

    • 내 코드: if-else 조건문
    • 해설 코드: 삼항 연산자 (d == 'R' ? 1 : -1)

  4. 결과 출력

    • 내 코드: 조건문으로 -1 처리
    • 해설 코드: 초기값 -1 활용

⚡️ 시간복잡도

  • 이동 기록: O(total_time)
  • 만나는 시점 탐색: O(total_time)
  • 전체 시간복잡도: O(total_time)

💭 회고

시뮬레이션 문제에서 각 객체의 시간별 상태를 기록하는 것이 핵심입니다. 이 문제를 통해 시간에 따른 상태 변화를 배열에 기록하는 테크닉을 익힐 수 있었습니다. 이러한 접근 방식은 다른 시뮬레이션 문제에서도 자주 활용될 수 있을 것 같습니다.