고양이는 많을수록 좋다
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 3728 | 1468 | 1258 | 39.685% |
문제
마법소녀인 마도카는 너무나도 고양이를 좋아하는 나머지 마법을 이용하여 고양이 $N$마리를 집에서 키우기로 결심했다!
마도카는 한 번의 행동에서 다음 $2$가지 마법 중 하나를 선택하여 사용한다. 처음에는 마도카의 집에 고양이가 존재하지 않는다.
- 생성 마법: 고양이 $1$마리를 마도카의 집에 생성한다.
- 복제 마법: 마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다. 즉, 만약 현재 마도카의 집에 고양이가 $k$마리 존재한다면, $0$마리 이상 $k$마리 이하의 고양이를 마도카의 집에 추가할 수 있다.
마도카는 위의 $2$가지 마법을 적절히 사용하여, 최소의 행동 횟수로 마도카의 집에 정확히 $N$마리의 고양이가 있도록 만들고 싶다. 계산을 어려워하는 마도카를 위해 최소의 행동 횟수를 계산해주자!
입력
첫 번째 줄에 키우기를 원하는 고양이의 수 $N(0\leq N\leq 10^{12})$이 정수로 주어진다.
출력
첫 번째 줄에 정확히 $N$마리의 고양이를 마도카의 집에 들일 수 있는 최소의 행동 횟수를 출력한다.
풀이
문제를 해결할 때 가장 중요한 부분은 복제 마법을 어떻게 활용할 것인가였다. 문제에서 0마리 이상 k마리 이하를 복제할 수 있다고 했지만, 최적의 전략을 생각해 보면 현재 있는 고양이를 전부 복제하는 것이 항상 유리하다. 왜냐하면 한 번의 복제로 가장 빠르게 고양이 수를 증가시킬 수 있기 때문이다. 결국 이 문제는 고양이를 1마리씩 늘리거나, 현재 있는 수를 2배로 늘릴 수 있을 때, 최소한의 행동으로 N마리를 만드는 문제라고 볼 수 있다.
처음엔 0마리에서 시작해 N마리로 맞춰가는 방식으로 접근했지만, 반대로 N에서 0으로 내려오는 방식이 더 직관적이고 편리했다. 2배로 나누면서 내려오고, 만약 나눈 값이 홀수라면 1번 더 증가하는 식으로 처리했다. 이렇게 하면 항상 최소 연산으로 도달할 수 있다. 특히 3마리 이하에서는 남은 마리 수만큼 행동해야 하므로, 이 부분을 별도로 처리하여 최적화했다.
package test.code;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(reader.readLine());
int cnt = 0;
while (n > 3) {
cnt++;
n = n/2 + (n%2==1?1:0);
}
System.out.println(cnt + n);
}
}