[자바] 백준 27961 - 고양이는 많을수록 좋다 (java)

목차

문제 : boj27961

 

 

필요 알고리즘

• 그리디
  
  • 0마리 이상 k마리 이하에 안낚이도록 그리디 규칙을 정할 수 있어야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  주의해야하는 점은 복제 마법 부분이다. 0마리 이상 k마리 이하라고 했는데, k마리 복제하지 않는게 이득인 경우가 과연 있을까? 없다(갯수 안넘어가게 조절할 때 빼고). 즉 이 문제는 고양이를 1마리 늘리거나, 2배 늘릴 수 있을 때 최소의 행동을 구하는 문제라고 보면 된다.

 

  이 때, 0마리부터 시작해 N마리를 맞춰가려면 2배씩 늘릴 때 갯수를 맞추기 위해 갯수를 조절하는 부분이 상당히 처리가 귀찮아진다. 그러므로 N마리에서 시작해 0마리로 내려오는게 더 편하다. 2배로 나누고, 나눈 값이 홀수라면 1번 더 더해준다(2배씩 내려오는게 항상 이득이므로). 내 경우엔 3마리 이상일 때 까지만 처리했는데, 3마리 이하라면 무조건 해당 마리수만큼의 동작이 필요하기 때문이다.

 

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        long n = Long.parseLong(br.readLine());
        int cnt = 0;
        while (n > 3) {
            cnt++;
            n = n/2 + (n%2==1?1:0);
        }
        System.out.println(cnt + n);
    }
}