[99클럽 코테스터디 16일차 TIL / 백준] 27961 - 고양이는 많을 수록 좋다 (그리디)

99클럽 코테스터디 16일차 TIL
KeyWord : 그리디

문제

마법소녀인 마도카는 너무나도 고양이를 좋아하는 나머지 마법을 이용하여 고양이 N$N$마리를 집에서 키우기로 결심했다!

마도카는 한 번의 행동에서 다음 $2$가지 마법 중 하나를 선택하여 사용한다. 처음에는 마도카의 집에 고양이가 존재하지 않는다.

• 생성 마법: 고양이 $1$마리를 마도카의 집에 생성한다.
• 복제 마법: 마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다. 즉, 만약 현재 마도카의 집에 고양이가 $k$마리 존재한다면, $0$마리 이상 $k$마리 이하의 고양이를 마도카의 집에 추가할 수 있다.

마도카는 위의 $2$가지 마법을 적절히 사용하여, 최소의 행동 횟수로 마도카의 집에 정확히 $N$마리의 고양이가 있도록 만들고 싶다. 계산을 어려워하는 마도카를 위해 최소의 행동 횟수를 계산해주자!

입력

첫 번째 줄에 키우기를 원하는 고양이의 수 $N(0\leq N\leq 10^{12})$이 정수로 주어진다.

출력

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

 

---

 

풀이

매우 기초적인 그리디 문제였다.

로직은 아래와 같다.

1. 생성 마법 $1$번 : 초기 고양이는 0마리이므로 복제마법이 불가능하다.
2. 복제마법 $k-1$번 : 고양이 수를 계속 2배로 늘린다.
3. 최초로 고양이 수가 N 이상이 되면 문제의 해를 찾게 된다.

여기서 2번 사항이 이 문제가 그리디인 이유이다.

일단 무조건 욕심내어 최댓값인 2배씩 고양이의 수를 증가시키다보면, 문제의 해를 구할 수 있다는 점에서 그렇다.

주의할 점은 2가지 정도 있었다.

• 입력 값인 N의 범위가 int 자료형의 범위를 초과할 수 있다.
• N이 0일 경우에는 예외적으로 0을 출력해주어야 한다.

 

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  

public class Main {  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        long N = Long.parseLong(br.readLine());  

        long answer = 1L;  
        long cnt = 1L; // 생성마법 1번  

        while (cnt < N) {  
            answer++;  
            cnt *= 2;  
        }  

        System.out.println(N == 0 ? 0 : answer);  
    }  
}

 

---

 

여담

처음에 문제 제대로 안 읽고 복제 마법은 무조건 2배로 늘리는 거구나 생각했다가 틀렸더랬다.

 

문제 좀 꼼꼼히 읽고 풀자! 괜히 시간 낭비하지 말고.