BOJ 3578 - Holes

문제

BOJ 3578 - Holes

숫자의 구멍(hole) 개수가 h일 때, 정확히 h개의 구멍을 가진 가장 작은 수를 구하라. 0,4,6,9는 구멍 1개, 8은 구멍 2개이다.

입력

정수 h가 주어진다.

출력

정확히 h개의 구멍을 가진 가장 작은 양의 정수를 출력한다.

예제

풀이

그리디하게 8(구멍 2개)을 최대한 사용하여 자릿수를 최소화한다.

1. h가 0이면 구멍이 없는 가장 작은 수 1을 출력한다
2. h가 1이면 구멍 1개인 가장 작은 수 0(양의 정수이므로 4 등)을 출력한다. 코드에서는 0을 출력
3. h가 홀수이면 맨 앞에 4(구멍 1개)를 놓고, 나머지를 8로 채운다
4. h가 짝수이면 전부 8로 채운다

핵심 아이디어: 8은 구멍 2개로 자릿수 대비 효율이 가장 높으므로, 8을 최대한 사용하고 홀수 잔여분은 4로 처리한다.

코드

#include <iostream>
 
using namespace std;
 
int h;
int main()
{
  cin >> h;
  if (!h)
  {
    cout << 1;
    return 0;
  }
  if (h == 1)
  {
    cout << 0;
    return 0;
  }
 
  if (h % 2)
    cout << 4;
  for (int i = 0; i < h / 2; i++)
    cout << 8;
}

복잡도

• 시간: O(h)
• 공간: O(1)