백준 20361번 [일우는 야바위꾼](C++) -yes6686- 티스토리

백준 문제 풀이: 20361 [일우는 야바위꾼]

---

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

문제 설명:

n개의 컵 중 하나에 공이 들어있습니다. 초기 공의 위치는 x이며, k번의 컵 위치 교환이 주어졌을 때 최종적으로 공이 들어있는 위치를 출력하는 문제입니다.

각 교환은 두 컵 a와 b의 위치를 바꾸는 작업입니다. 교환 과정에서 공의 위치가 교환된 컵 중 하나라면, 공의 위치도 변경됩니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

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

    int n, x, k;
    cin >> n >> x >> k; // 컵의 개수, 초기 공의 위치, 교환 횟수

    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b; // 두 컵의 위치 입력
        if (x == a) {
            // 공이 a 위치에 있으면 b로 이동
            x = b;
        } else if (x == b) {
            // 공이 b 위치에 있으면 a로 이동
            x = a;
        }
    }

    // 최종 공의 위치 출력
    cout << x;
    return 0;
}

---

코드 설명

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

• 핵심 알고리즘:
  • 공의 위치를 추적하면서 두 컵의 교환 작업을 시뮬레이션합니다.
  • 공의 현재 위치가 교환되는 컵 중 하나와 같다면 공의 위치를 반대쪽 컵으로 업데이트합니다.
• 구현 세부사항:
  • x: 현재 공의 위치를 나타내는 변수입니다.
  • 각 교환 작업에서 공의 위치가 교환된 컵 중 하나라면, 공의 위치를 반대쪽 컵으로 이동시킵니다.
  • 입력이 끝난 후 최종적으로 공의 위치를 출력합니다.
• 시간 복잡도 분석:
  • 교환 작업은 총 k번 수행되며, 각 작업은 O(1)에 처리됩니다.
  • 전체 시간 복잡도는 O(k)입니다.

---

결과

입력된 교환 작업을 정확히 시뮬레이션하여 최종 공의 위치를 출력합니다.

해당 문제에 대한 다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!