문제
You may have seen a mechanic typewriter — such devices were widespread just 15 years ago, before computers replaced them. It is a very simple thing. You strike a key on the typewriter keyboard, the corresponding type bar rises, and the metallic letter molded into the type bar strikes the paper. The art of typewriter typing, however, is more complicated than the art of computer typing. You should strike keys with some force otherwise the prints will not be dark enough. Also you should not overdo it otherwise the paper will be damaged.
Imagine a typewriter with very sharp letters, which cut the paper instead of printing. It is clear that digit 0 being typed on the typewriter makes a nice hole in the paper and you receive a small paper oval as a bonus. The same happens with some other digits: 4, 6, 9 produce one hole, and 8 produces two touching holes. The remaining digits just cut the paper without making holes.
The Jury thinks about some exhibition devoted to the oncoming jubilee of Pascal language. One of the ideas is to make an art installation, consisting of an empty sheet of paper with exactly h (0 ≤ h ≤ 510) holes made by typing a non-negative integer number on the cutting typewriter described above. The number must be minimal possible and should not have leading zeroes. Unluckily we are too busy with preparing the ACM quarter- and semifinals, so we need your help and ask you to write a computer program to generate the required number.
입력
A single integer number h — the number of holes.
출력
The integer number which should be typed.
풀이
입력으로 주어지는 수 h에 대해 h개의 구멍이 뚫리도록 타자기를 치면 되는문제다.
0부터 시작하면 안되며, 최솟값이어야 한다.
아래는 문제에서 주어진 예시다.
- 0인 경우 1개
- 4, 6, 9의 경우 1개
- 8의 경우 2개
- 나머지 수는 0개
위와 같은 조건을 통해 나머지 수들에 대해서 아래와 같이 정리할 수 있다.
- h = 0일 때 [1], (1, 2, 3, 5, 7 중 최솟값)
- h = 1일 때 [0]
h가 짝수인 경우 [8] (8, 44, 46, 49, 64, ... 중 최솟값)로 구멍을 뚫는게 최솟값이다.
때문에 1개를 먼저 찍은 후 나머지를 8로 처리하는 방법이 최선이다.
0부터는 시작할 수 없으므로 4를 찍어주자.
- h >= 3, h가 홀수일 때 우선 [4]
- h >= 2, h가 짝수일 때 h/2 * [8], (8, 44, 46, 49, 64, ... 중 최솟값)
소스코드
출처
3578번: Holes
You may have seen a mechanic typewriter — such devices were widespread just 15 years ago, before computers replaced them. It is a very simple thing. You strike a key on the typewriter keyboard, the corresponding type bar rises, and the metallic letter mo
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 04084] Viva la Diferencia [Java] (1) | 2023.12.02 |
|---|---|
| [백준 03554] Enigmatic Device [Java] (1) | 2023.12.01 |
| [백준 03533] Explicit Formula [Java] (0) | 2023.11.29 |
| [백준 03512] Flat [Java] (0) | 2023.11.27 |
| [백준 03507] Automated Telephone Exchange [Java] (1) | 2023.11.27 |