백준 31287번 [장난감 강아지](C++) -yes6686- 티스토리

백준 문제 풀이: 31287 (장난감 강아지)

---

문제 링크: https://www.acmicpc.net/problem/31287

문제 설명:

장난감 강아지가 주어진 명령 문자열 s를 k번 반복하여 이동합니다. 명령어는 'U'(위로), 'D'(아래로), 'L'(왼쪽으로), 'R'(오른쪽으로)로 이루어져 있습니다. 강아지가 원점(0, 0)으로 돌아오는 경우 "YES"를 출력하고, 그렇지 않으면 "NO"를 출력합니다. 최대 반복 횟수 k는 1000번까지만 고려합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    int x = 0, y = 0; // 현재 좌표
    int dx = 0, dy = 0; // 한 사이클의 총 이동량

    // 한 사이클에서의 최종 이동 계산
    for (char c : s) {
        if (c == 'U') dy -= 1;
        else if (c == 'D') dy += 1;
        else if (c == 'L') dx -= 1;
        else if (c == 'R') dx += 1;
    }

    // 전체 이동 후의 위치 계산
    for (int i = 0; i < k && i < 1000; i++) {
        for (char c : s) {
            if (c == 'U') y -= 1;
            else if (c == 'D') y += 1;
            else if (c == 'L') x -= 1;
            else if (c == 'R') x += 1;
            if (x == 0 && y == 0) { // 원점으로 돌아오면 즉시 종료
                cout << "YES\n";
                return 0;
            }
        }
    }

    // 원점으로 돌아오지 못한 경우
    cout << "NO\n";
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 주어진 명령 문자열을 반복하며 강아지의 위치를 추적합니다. 위치가 (0, 0)으로 돌아오면 즉시 "YES"를 출력합니다.
• 구현 세부사항:
  • dx와 dy: 명령어의 이동 방향을 나타냅니다.
  • 한 사이클에서의 이동량을 계산한 후, 매 반복마다 위치를 갱신하며 원점 여부를 확인합니다.
  • 최대 1000번 반복 조건을 설정하여 시간 초과를 방지합니다.
• 시간 복잡도 분석:
  • 명령 문자열의 길이가 n, 최대 반복 횟수가 k일 때, 최악의 경우 O(n × k)입니다.
  • 반복 횟수가 1000으로 제한되므로, 시간 복잡도는 O(n × 1000)로 제한됩니다.

---

결과

강아지가 주어진 명령 문자열을 k번 반복하여 원점으로 돌아오는지 여부를 정확히 판단합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!