[그리디][Java][BOJ] #27961. 고양이는 많을수록 좋다

#그리디  #Bronze1

https://www.acmicpc.net/problem/27961

 

🌷 문제 설명

✏️ 백준 연습문제: #4949. 균형잡힌 세상
마법소녀인 마도카는 너무나도 고양이를 좋아하는 나머지 마법을 이용하여 고양이 $N$마리를 집에서 키우기로 결심했다! 마도카는 한 번의 행동에서 다음 $2$가지 마법 중 하나를 선택하여 사용한다. 처음에는 마도카의 집에 고양이가 존재하지 않는다. 생성 마법: 고양이 $1$마리를 마도카의 집에 생성한다. 복제 마법: 마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다. 즉, 만약 현재 마도카의 집에 고양이가 $k$마리 존재한다면, $0$마리 이상 $k$마리 이하의 고양이를 마도카의 집에 추가할 수 있다. 마도카는 위의 $2$가지 마법을 적절히 사용하여, 최소의 행동 횟수로 마도카의 집에 정확히 $N$마리의 고양이가 있도록 만들고 싶다. 계산을 어려워하는 마도카를 위해 최소의 행동 횟수를 계산해주자!

⌨️ 입력
첫 번째 줄에 키우기를 원하는 고양이의 수 N(0 <= N <= 10^12)이 정수로 주어진다.

🖨️ 출력
첫 번째 줄에 정확히 N마리의 고양이를 마도카의 집에 들일 수 있는 최소의 행동 횟수를 출력한다.

입출력 예

입력	출력
1	1
6	4
2147483648​	32

 

💡 해결 포인트

1.  log로 못품
- 처음엔 입력값에 미치지 않는 가장 큰 2^n 에서의 n에다가
- 0에서 1 생기는 마법 +1
- 2^n과 입력값 차이 메꾸는 복사마법 +1 해서
- n + 2 하면 답이 나올 거라고 생각했다... 그래서 로그 이용해서 풀면되는줄알았는데 아무리 해도 안됨
- 🤖 부동소수점 오차 때문이라고, 비트를 이용해서 계산을 하라고 하는 순간 다 내려놓고 그냥 반복문 돌림 

2. 그래서 곱하기 함
- 1 부터 2를 곱해가면서 입력값보다 작을때까지 반복문을 돌림
- 곱하려면 일단 시작점이 0이 아니어야되니까, 1부터 시작하고 (0에서 1생기는 부분)
- 그래서 그 카운트에다가 2^n 과 입력값 차이 메꾸는 복사마법 +1 해서 겨우 함

3. int의 범위
- 2^31 == 2147483647
- long을 쓰자

4. 0이 나올때도 있다
- ㅎㅎ 너무 당연한데 놓치면 잘 안보임

 

🌷 내 코드

1. 그리디(?)

import java.io.*;
import java.util.*;

public class BOJ_27961 {
  public static void main(String[] args) throws IOException {
    System.setIn(new FileInputStream("example.txt"));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    long N = Long.parseLong(br.readLine());

    if (N == 0) { // 0일 때
      System.out.println(0);
      return;
    }

    int count = 0; 
    long num = 1;

    while (num < N) { 
      num *= 2; 
      count++;
    }

    System.out.println(count+1); // 0부터 시작하니까 +1
  }  
}

 

🌷 코멘트

로그 생각해냈을때만해도 내가 천잰줄ㅋㅋㅋ 이게 브론즈라니
근데 이게 왜 그리디야?

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com