BOJ 4927 - Casting Out Nines

문제

A op B = C 형태(op는 + 또는 *, 종료 문자는 .)의 수식이 주어질 때, 9로 나눈 나머지 검사(casting out nines)를 통해 PASS/NOT!을 출력한다.

풀이

어떤 수의 각 자리 합은 그 수를 9로 나눈 나머지와 같다(digit root). 이를 이용해 A, B, C를 자릿수 합으로 환산한 뒤 op에 따라 (A%9 op B%9) % 9 == C % 9이면 PASS, 아니면 NOT!으로 판단한다.

코드

#include <iostream>
#include <string>
 
using namespace std;
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
 
  string s;
  for (int tc = 1; cin >> s && s != "."; ++tc) {
    cout << tc << ". ";
 
    int pos = 0;
    int A = 0;
    while (s[pos] != '*' && s[pos] != '+') {
      A += s[pos] - '0';
      pos++;
    }
 
    char op = s[pos++];
 
    int B = 0;
    while (s[pos] != '=') {
      B += s[pos] - '0';
      pos++;
    }
 
    pos++;
 
    int C = 0;
    while (s[pos] != '.') {
      C += s[pos] - '0';
      pos++;
    }
 
    int res = (op == '*' ? (A % 9) * (B % 9) : (A % 9) + (B % 9));
    if (res % 9 == C % 9) cout << "PASS\n";
    else cout << "NOT!\n";
  }
 
  return 0;
}

복잡도

시간: O(수식 길이)
공간: O(1)

문제

풀이

코드

복잡도

최근 글