백준 12927번 [배수 스위치](C++) -yes6686- 티스토리

백준 문제 풀이: 12927 [배수 스위치]

---

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

문제 설명:

스위치가 켜짐(Y) 또는 꺼짐(N) 상태로 배열되어 있습니다. 각 스위치 i에 대해 i의 배수 위치의 스위치를 토글(켜짐 → 꺼짐, 꺼짐 → 켜짐)합니다. 모든 스위치를 끄기 위해 필요한 최소 횟수를 구하세요.

---

문제 해결 코드

// 백준 12927 - 배수 스위치
#include <iostream>
using namespace std;

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

    string s;
    cin >> s; // 스위치 상태 입력
    int cnt = 0; // 조작 횟수

    // 모든 스위치 확인
    for (int i = 1; i <= s.size(); i++) {
        if (s[i - 1] == 'N') continue; // 꺼진 상태면 무시
        cnt++; // 조작 횟수 증가

        // i의 배수 위치의 스위치 토글
        for (int j = i; j <= s.size(); j += i) {
            s[j - 1] = (s[j - 1] == 'N') ? 'Y' : 'N';
        }
    }

    cout << cnt << '\n'; // 최소 조작 횟수 출력
    return 0;
}

---

코드 설명

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

• 핵심 알고리즘:
  • 모든 스위치를 순차적으로 확인하면서 켜져 있는 스위치를 발견할 경우, 해당 스위치와 그 배수 위치의 스위치를 토글합니다.
• 구현 세부사항:
  • s[i - 1]: 인덱스 보정을 통해 1부터 시작하는 문제 조건을 만족시킵니다.
  • 내부 for 루프에서 j += i를 사용하여 i의 배수 위치를 탐색합니다.
  • 스위치 상태를 토글할 때 삼항 연산자를 사용하여 'N'과 'Y'를 전환합니다.
• 시간 복잡도 분석:
  • 최대 O(n log n): 외부 루프는 O(n), 내부 루프는 약 O(log n)에 비례합니다.

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

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