수조의 물 줄이기
문제
한 실험실에는 물이 담긴 수조가 하나 있다. 지금 수조에는 물이 정확히 N리터 담겨 있다.
연구원은 이 수조의 물을 정확히 1리터만 남기려고 한다. 연구원이 쓸 수 있는 조작은 다음의 세 가지뿐이다.
| 조작 | 하는 일 | 쓸 수 있는 조건 |
|---|---|---|
| 1번 조작 | 물의 양을 3분의 1로 줄인다 | 지금 물의 양이 3으로 나누어떨어질 때 |
| 2번 조작 | 물의 양을 2분의 1로 줄인다 | 지금 물의 양이 2로 나누어떨어질 때 |
| 3번 조작 | 물을 1리터 버린다 | 언제나 |
조작을 한 번 할 때마다 횟수가 1씩 늘어난다. 연구원은 조작 횟수를 되도록 적게 하여 수조의 물을 1리터로 만들고 싶다.
처음에 담긴 물의 양 N이 주어졌을 때, 물을 정확히 1리터로 만들기 위한 조작 횟수의 최솟값을 계산하는 프로그램을 작성하여라.
예를 들어 N=10인 상황을 가정하자. 다음과 같이 조작하면 세 번 만에 1리터가 된다.
| 순서 | 처음 | 1번째 조작 뒤 | 2번째 조작 뒤 | 3번째 조작 뒤 |
|---|---|---|---|---|
| 쓴 조작 | 3번 조작 | 1번 조작 | 1번 조작 | |
| 물의 양 | 10 | 9 | 3 | 1 |
처음에 2번 조작으로 10리터를 5리터로 줄이는 방법도 생각할 수 있다. 그런데 5리터는 2로도 3으로도 나누어떨어지지 않으므로 3번 조작으로 4리터를 만들어야 하고, 이어서 2리터, 1리터를 거치게 되어 모두 네 번이 걸린다. 이 과정을 표로 적으면 다음과 같다.
| 순서 | 처음 | 1번째 조작 뒤 | 2번째 조작 뒤 | 3번째 조작 뒤 | 4번째 조작 뒤 |
|---|---|---|---|---|---|
| 쓴 조작 | 2번 조작 | 3번 조작 | 2번 조작 | 2번 조작 | |
| 물의 양 | 10 | 5 | 4 | 2 | 1 |
네 번은 세 번보다 많으므로 좋은 방법이 아니다. 세 번보다 적게 걸리는 방법은 없으므로, 현재 예시에서의 정답은 3이다.
조작을 고를 때마다 당장 물을 많이 줄이는 쪽을 택하는 것이 늘 좋은 것은 아니라는 점을 짚어 두자. 10리터에서 3분의 1로 줄이는 조작을 쓰지 못하니 2분의 1로 줄이는 쪽이 유리해 보이지만, 실제로는 1리터를 먼저 버려서 9리터를 만드는 쪽이 더 적게 걸린다.
입출력 예시
예시 1
입력
10
출력
3
예시 2
입력
1
출력
0
예시 3
입력
1000000
출력
19
입력 조건
가장 먼저 첫째 줄에 수조에 담긴 물의 양 N이 주어진다. N은 1 이상 1,000,000 이하의 자연수이며 단위는 리터다. 입력은 이 한 줄로 끝난다. 쓸 수 있는 조작의 종류는 입력으로 주어지지 않고, 본문에 적어 둔 세 가지로 늘 같다.
출력 조건
수조의 물을 정확히 1리터로 만들기 위한 조작 횟수의 최솟값을 한 줄에 출력한다. 처음부터 물이 1리터인 경우에는 조작이 필요하지 않으므로 0을 출력한다.
요구사항
- 3분의 1로 줄이는 조작은 지금 물의 양이 3으로 나누어떨어질 때만 쓸 수 있습니다
- 2분의 1로 줄이는 조작은 지금 물의 양이 2로 나누어떨어질 때만 쓸 수 있습니다
- 1리터를 버리는 조작은 언제나 쓸 수 있습니다
- 목표는 정확히 1리터입니다. 1리터보다 적게 만들어서는 안 됩니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
1
0
10
3
1000000
19
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.