[BAEKJOON]27961 고양이는 많을수록 좋다

문제 요약

• 알고리즘 분류: 그리디
• 난이도: Broze1
• 문제내용:
  • 다음중 2가지 마법만 사용 할수있다.
    • 생성 마법: 고양이 1$1$마리를 마도카의 집에 생성한다.
    • 복제 마법: 현재 k개 있으면 k마리 이하만 복제 가능하다.

• 사이트: https://www.acmicpc.net/problem/27961

문제풀이

 이번 문제는 전체 경우의 수를 탐색하기에는 10^12승 숫자 만큼 탐색하면 시간 초과가 나서 안될것이다. 그래서 O(logN)만큼 나오도록 구현 해야 한다. 그래서 이 문제는 그리디로 접근해야 한다. 그리디에 관련 내용은 아래글에서 확인해보면된다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

문제 접근 방법

 그리디 같은 문제는 구현 보다 사고력을 요구하는 문제이다. 그래서 구현보다 어떻게 접근하는지만 알면 된다. 이번 문제에서 글을 보면 복제 마법에 대한 내용 보면 내가 같고 있는 고양이 개수가 K마 이면 K마리 이하로 복제가 된다고 보면된다. 그럼 내가 최대만큼 복재하면 K*2마리가 나온다고 볼수 있다. 그럼 N개 이하 만큼 계속 k*2만큼 생성하고 남은 고양이 마리수만 복제 하면된다. 그럼 최소 마법 쓰는 횟수는 아래와 같이 정의 할수 있다.

Log2(N) 에서 올림 처리만 하면 된다.

그럼 2 ^ x부분에 N이 딱 맞게 갈수 있지만 아닌 경우도 있어서 그 나머지는 +1로 채워줘야 지 최소 횟수가 나온다. 그래서 Log2(N)에서 정수나올수 있지만 실수 나오면 올림하면 +1로 대책이 가능하다고 볼수 있다. 나머지 부분은 아래 코드를 참고 하면된다.

Code

 이번 문제에서는 Math모듈에서 log를 제공 해서 log로 푼 문제와 2^x에서 x를 구하기 위해서 반복문으로 처리한 것이 있다.

python

import math

N = int(input())
print(math.ceil(round(math.log(N, 2), 10)) + 1 if N > 0 else 0)

Java

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());
		int count = 0;

		if(N > 0){
			count = 1;
			Long K = 1l;
			while(K < N){
				K *= 2;
				count++;
			}
		}

		System.out.println(count);

	}
}