[백준 | Java] 27961번 고양이는 많을수록 좋다
❓ 고양이는 많을수록 좋다
🏷️ 관련 주제 : 수학 Greedy Algorithm
💦 나의 시도
로그를 사용한 방법
마도카가 사용할 수 있는 마법으로 생성 마법과 복제 마법이 있는데복제 마법은 일부 또는 전부를 대상으로 복제하므로 1마리만도 복제 가능합니다.
즉, N이 0보다 클 때, 맨 처음 생성 마법을 사용한 이후로는 복제 마법만 사용한다고 생각하고 문제를 풀면 될 것이라고 생각하였습니다.
$ 0 \leq N \leq 10^{12}$
- N이 0인 경우,
0출력 - N이 1인 경우,
생성 마법1회 $\rightarrow$1출력 - N이 1 초과인 경우,
생성 마법1회 +복제 마법m번 실행 $\rightarrow$m + 1출력- $2^{m-1} \lt N \leq 2^m$
m을 구하기 위해 양변에 로그를 취하면
$log{2^{m-1}} \lt log{N} \leq log{2^m} \quad (1 \leq m, \ 1 \leq 2^{m - 1} \lt N \leq 2^m)$
$(m-1)log{2} \lt log{N} \leq mlog{2}$
$m - 1 \lt \frac{long{N}}{long{2}} \leq m$
$m - 1 \lt log_{2}{N} \leq m \quad (m - 1, m \in \N)$
그래서 Math.log()를 이용하여 $log_{2}{N}$을 구하고Math.ceil() 메서드를 사용하여 결과값을 올림하여 m을 구하고자 하였습니다.
Math.ceil(Math.log(N) / Math.log(2) + 1)
과 같이 결과값을 구하고 출력하고자 하였는데...
❌ 틀렸습니다.
코드의 테스트 케이스 2147483648 입력 시, 32가 출력되어야 하는데 33이 출력되는 문제가 있었습니다.
$log_{2}{2147483648} = 31$이 나와야 하는데Math.log(N) / Math.log(2) = 31.000000000000004가 나와서
문제를 해결하지 못하였습니다.
일단, 반복문을 사용한 방법을 통해 제출을 성공하고
그래도 이 방법을 포기할 수 없어서 다른 블로그에 자바로 밑이 2인 로그 계산하는 법을 찾아보았습니다.
그 결과 Math.log()가 아닌 밑이 10인 로그 Math.log10()을 사용하는 방법이 있다는 것을 알게되었습니다.
double total = Math.log10(N) / Math.log10(2);
System.out.println((long) Math.ceil(total) + 1);로 코드를 수정하였고 제출 성공하였습니다.
반복문을 사용한 방법
- N이 0인 경우, 0 출력
- N이 1인 경우, 1 출력
- N이 그 이상인 경우, 반복문을 통해 1에 2를 거듭 곱하면서 2를 곱한 횟수를 세고
그 결과값이 N을 초과한 경우, 횟수를 출력
📑제출 기록 및 오답 원인
첫번째 제출 성공한 것이 반복문을 사용한 방법
두번째 제출 성공한 것이 로그를 사용한 방법입니다.
💯 해결 방법
반복문을 사용한 방법
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long N = sc.nextLong();
if (N == 0) {
System.out.println(0);
return;
}
long total = 1;
int cnt = 1;
while (total < N) {
total *= 2;
cnt++;
}
System.out.println(cnt);
}
}로그를 사용한 방법
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long N = sc.nextLong();
if (N == 0) {
System.out.println(0);
return;
}
double total = Math.log10(N) / Math.log10(2);
System.out.println((long) Math.ceil(total) + 1);
}
}