백준 9546번 [3000번 버스](C++) -yes6686- 티스토리

백준 문제 풀이: 9546번 [3000번 버스]

---

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

문제 설명:

3000번 버스는 특정 규칙을 따라 손님을 태웁니다. N개의 정류장을 거치며, 각 정류장에서 태운 손님 수는 이전까지 태운 손님 수의 두 배에 1을 더한 값입니다. 처음에는 손님을 태우지 않습니다. 각 테스트 케이스마다 마지막 정류장에서 버스에 있는 손님의 수를 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

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

    int T; // 테스트 케이스 수
    cin >> T;
    while (T--) {
        int n; // 정류장 수
        cin >> n;

        int ans = 0; // 마지막 정류장에서의 손님 수
        for (int i = 0; i < n; i++) {
            ans = (ans * 2 + 1); // 손님 수 계산
        }

        cout << ans << '\n'; // 결과 출력
    }
}

---

코드 설명

위 코드는 각 정류장에서 손님 수를 계산하는 규칙에 따라 마지막 정류장에서의 손님 수를 출력합니다. 주요 로직은 다음과 같습니다:

1. 초기값 설정: 처음에는 버스에 손님이 없으므로 `ans`를 0으로 초기화합니다.
2. 손님 수 계산: 각 정류장에서 `ans = ans * 2 + 1` 규칙을 적용하여 손님 수를 업데이트합니다.
3. 결과 출력: 계산된 마지막 정류장에서의 손님 수를 출력합니다.

시간 복잡도:

• 각 테스트 케이스마다 O(N)의 복잡도를 가지며, N은 정류장의 수입니다.
• 전체 복잡도는 O(T × N)입니다. 여기서 T는 테스트 케이스 수입니다.

---

결과

위 코드는 테스트 케이스에 따라 3000번 버스의 마지막 정류장에서 손님 수를 정확히 계산하고 출력합니다. 추가적인 최적화나 대체 구현 방안이 있다면 댓글로 의견을 남겨주세요!