BOJ 4539 - 반올림

문제

주어진 수를 일의 자리부터 차례대로 반올림하여 가장 높은 유효 자릿수만 남긴 결과를 출력하라.

입력

테스트 케이스 수 N, 각 케이스마다 양의 정수가 주어진다.

출력

반올림 결과를 출력한다.

예제

입력	출력
`3` `1` `14` `332`	`1` `10` `300`

풀이

일의 자리부터 최상위까지 반복적으로 반올림한다.

자릿수 단위 i를 10부터 시작한다
현재 자릿수가 5 이상이면 올림((X/i + 1) * i), 미만이면 버림(X/i * i)한다
i를 10배씩 증가시키며 i < X인 동안 반복한다

핵심 아이디어: 낮은 자릿수부터 순차적으로 반올림하면 올림이 상위 자릿수에 전파될 수 있어, 최종적으로 최상위 자릿수만 남게 된다.

코드

#include <iostream>
using namespace std;
#define endl '\n'
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
 
  while (N--)
  {
    int X;
    cin >> X;
 
    for (int i = 10; i < X; i *= 10)
    {
      if (X % i / (i / 10) >= 5)
      {
        X = (X / i + 1) * i;
      }
      else
      {
        X = X / i * i;
      }
    }
    cout << X << endl;
  }
}

복잡도

시간: O(N * d) (d: 자릿수)
공간: O(1)

문제