BOJ 2033 - 반올림

문제

BOJ 2033 - 반올림

양의 정수가 주어질 때, 일의 자리부터 반올림을 반복하되 해당 자릿수가 0이 아닌 동안 계속한다.

입력

양의 정수 N이 주어진다.

출력

반올림을 반복한 결과를 출력한다.

예제

풀이

자릿수 단위를 10부터 시작하여 10배씩 키워가며 반올림을 반복한다.

1. 단위 tmp = 10에서 시작한다
2. n >= tmp인 동안 반복한다 (현재 단위 이상의 자릿수가 남아 있을 때)
3. 현재 단위의 나머지가 절반 이상이면 올림, 아니면 버림 처리한다
4. 단위를 10배로 키우고 반복한다

핵심 아이디어: 반올림을 낮은 자릿수부터 적용하면 캐리가 전파되므로, 매 단계에서 나머지를 확인하여 올림/버림을 결정하는 시뮬레이션으로 O(log N)에 해결된다.

코드

#include <iostream>
using namespace std;
int main()
{
  long long n;
  cin >> n;
 
  long long tmp = 10;
 
  while (n >= tmp)
  {
    (n % tmp) >= tmp / 2 ? n = ((long long)((int)n / tmp) + 1) *tmp : n = ((long long)(int)n / tmp) * tmp;
    tmp *= 10;
  }
  cout << n << endl;
}

복잡도

• 시간: O(log N)
• 공간: O(1)