[Day13]JAVA- 백준 고양이는 많을수록 좋다(27961번)

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

 

 

백준의 고양이는 많을수록 좋다❤️ 문제는 그리디 알고리즘으로 최적의 선택을 구하는 것이다. 

근데 이 문제는 그리디 알고리즘이 무엇인지 몰라도 풀 수 있는 수준이다. 

 

N마리의 고양이를 만들기 위해서는 2가지 방법이 있다. 

1. 생성마법 : 1마리씩 추가

2. 복제마법 : 현재 k 마리가 존재하면 , 0~k 까지의 마리 수 추가 가능

 

최소한으로 마법을 부려야 하니 복제마법으로 크게크게 추가 하는 것이 최적의 선택이라는 것을 파악하면 된다. 

 

주의해야 할 점은 입력 값의 범위가 int 나 Integer을 사용하면 오류가 발생하는 범위 임으로 long으로 지정해줘야 한다. 

 

 

 

 

1. 생성마법으로 1마리 

2. 생성마법 혹은 복제 마법으로 (1+1) 2마리 

 

2마리까지는 기본이다. 

그 다음부터는 복제마법의 최고 값 (2*k) 이 원하는 고양이 수를 넘어설때까지 복제마법을 하는 것이다. 

N 을 넘어가는 순간 마지막 복제마법을 하고 끝나는 것이다. 

while(cat <N)
{
  if((cat*2) <= N)
  {
    //복제가 가능하면 
    cat += cat;
    count++;
  }
  else 
  {
     cat = N;
     count++;
  }
}

 

 

어려운 문제는 아니지만, 놓칠만한 부분은 범위지정 long 과 입력값 중 0 이 있어서 고양이를 원하지 않은 경우도 포함해야 한다. 

 

*최종코드 

import java.io.*;
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());

    if(N==1 || N==0){
      System.out.println(N);
      return;
    }

    //처음 2번 횟수로 2마리는 무조건 디폴트 
    long cat = 2;
    long count =2;    

    while(cat <N)
    {
      if((cat*2) <= N)
      {
        //복제가 가능하면 
        cat += cat;
        count++;
      }
      else 
      {
         cat = N;
         count++;
      }
    }

    System.out.println(count);
  }
  
}