백준 17253번 [삼삼한 수 2](C++) -yes6686- 티스토리

백준 문제 풀이: 17253 [삼삼한 수 2]

---

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

문제 설명:

양의 정수 x가 주어졌을 때, x가 삼삼한 수인지 판별하는 문제입니다. 삼삼한 수란, x를 3으로 나눈 나머지가 항상 0 또는 1인 수를 의미합니다.

문제의 핵심은 x를 3으로 나누며 나머지가 2인 경우가 나오면 "NO"를 출력하고, 끝까지 나머지가 0 또는 1로 유지되면 "YES"를 출력하는 것입니다.

---

문제 해결 코드

// C++로 구현된 코드
#include <iostream>
using namespace std;

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

    long long int x;
    cin >> x;

    // 0은 삼삼한 수가 아님
    if (x == 0) {
        cout << "NO";
        return 0;
    }

    // x를 3으로 나누며 확인
    while (x > 0) {
        if (x % 3 == 2) { // 나머지가 2인 경우
            cout << "NO";
            return 0;
        }
        x /= 3; // 3으로 나누기
    }

    // 모든 조건 통과 시 삼삼한 수
    cout << "YES";
    return 0;
}

---

코드 설명

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

• 핵심 알고리즘:
  • x를 3으로 나누며 나머지를 확인하는 반복문.
  • 삼진법 관점에서 x의 각 자리값이 0 또는 1로만 구성되어 있는지 확인합니다.
• 구현 세부사항:
  • 입력값 x가 0이면 삼삼한 수가 아니므로 바로 "NO"를 출력합니다.
  • 반복문에서 x % 3 값이 2인 경우를 발견하면 "NO"를 출력하고 종료합니다.
  • x가 0이 될 때까지 문제가 발생하지 않으면 "YES"를 출력합니다.
• 시간 복잡도 분석:
  • x를 반복적으로 3으로 나누므로, 반복 횟수는 O(log₃x)입니다.
  • 각 반복에서 나눗셈 및 나머지 연산은 상수 시간에 처리됩니다.
  • 전체 복잡도는 O(log₃x)로 매우 효율적입니다.

---

결과

입력값 x가 삼삼한 수인지 정확히 판별합니다.

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