BOJ 4892 - 숫자 맞추기 게임

문제

양의 정수에 3을 곱한 후, 홀짝에 따라 다른 연산을 수행하여 최종 결과와 홀짝 여부를 출력하라. 0 입력 시 종료.

입력

여러 줄에 양의 정수가 주어진다. 0이면 종료.

출력

순서 번호, 홀짝, 최종 결과를 출력한다.

예제

입력	출력
`3` `0`	`1. odd 1`

풀이

수학적 트릭을 순서대로 시뮬레이션한다.

N에 3을 곱한다
결과가 홀수이면 1을 더한 뒤 2로 나누고, 짝수이면 2로 나눈다
결과에 3을 곱하고 9로 나눈다
홀짝 여부와 결과를 순서 번호와 함께 출력한다

핵심 아이디어: 각 단계의 연산이 고정되어 있으므로 순서대로 수행하면 된다. 원래 수의 절반 근처 값이 복원된다.

코드

#include <iostream>
 
using namespace std;
 
int main()
{
  int n, i = 1;
 
  while (i)
  {
    cin >> n;
    if (n == 0)
      break;
    cout << i << ". ";
    n *= 3;
    if (n % 2)
    {
      cout << "odd ";
      n = (n + 1) / 2;
      n = 3 * n;
      n = n / 9;
      cout << n << "\n";
    }
    else
    {
      cout << "even ";
      n = n / 2;
      n = 3 * n;
      n = n / 9;
      cout << n << "\n";
    }
    i++;
  }
 
  return 0;
}

복잡도

시간: O(T) (T: 테스트 케이스 수)
공간: O(1)

문제