백준 1769번 [3의 배수](C++) -yes6686- 티스토리

백준 문제 풀이: 1769 [3의 배수]

---

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

문제 설명:

주어진 숫자가 3의 배수인지 확인하는 문제입니다. 숫자가 여러 자리일 경우, 각 자리 숫자의 합을 반복적으로 계산하여 한 자릿수가 될 때까지 과정을 진행합니다. 최종 결과가 3의 배수라면 "YES", 아니면 "NO"를 출력하며, 이 과정이 몇 번 수행되었는지도 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <string>
using namespace std;

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

    string s; // 입력 숫자
    cin >> s;
    int count = 0; // 합을 반복적으로 계산한 횟수

    while (true) {
        if (s.size() == 1) { // 한 자리 숫자가 되었을 때
            if (stoi(s) % 3 == 0) { // 3의 배수 여부 확인
                cout << count << '\n';
                cout << "YES" << '\n';
            } else {
                cout << count << '\n';
                cout << "NO" << '\n';
            }
            break;
        } else {
            int sum = 0;
            for (int i = 0; i < s.size(); i++) { // 각 자리 숫자의 합 계산
                sum += s[i] - '0';
            }
            s = to_string(sum); // 합을 문자열로 변환
            count++; // 계산 횟수 증가
        }
    }

    return 0;
}

예제 입력:

1234567

예제 출력:

3
NO

---

코드 설명

• 핵심 알고리즘: 숫자를 반복적으로 자리수의 합으로 변환하여 3의 배수 여부를 확인합니다.
• 구현 세부사항:
  • 문자열로 입력받아 각 자리수를 쉽게 접근합니다.
  • 자리수의 합을 계산하고, 이를 다시 문자열로 변환하여 과정을 반복합니다.
  • 한 자릿수가 되었을 때 3의 배수 여부를 판단합니다.
• 시간 복잡도:
  • 각 반복에서 자리수를 순회하므로 O(k), k는 현재 숫자의 자리수입니다.
  • 최대 반복 횟수는 입력 자리수가 1이 될 때까지이므로 전체 복잡도는 O(n), n은 초기 자리수의 길이입니다.

---

결과

입력된 숫자에 대해 3의 배수 여부와 이를 확인하는 과정에서의 반복 횟수를 정확히 계산하여 출력합니다. 문제는 문자열 처리와 반복 계산을 연습하기에 적합합니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!