[C#] 백준 27961번 고양이는 많을수록 좋다

[ 문제 ]

마법소녀인 마도카는 너무나도 고양이를 좋아하는 나머지 마법을 이용하여 고양이 N마리를 집에서 키우기로 결심했다! 마도카는 한 번의 행동에서 다음 2가지 마법 중 하나를 선택하여 사용한다. 처음에는 마도카의 집에 고양이가 존재하지 않는다.

 

- 생성 마법: 고양이 1마리를 마도카의 집에 생성한다.

- 복제 마법: 마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다.

(즉, 만약 현재 마도카의 집에 고양이가 k마리 존재한다면, 0마리 이상 k마리 이하의 고양이를 마도카의 집에 추가할 수 있다.)

 

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

 

[ 코드 ]

1. 내 코드

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

long n = long.Parse(sr.ReadLine());
int count = 0;

if (n <= 1)
{
    sw.Write(n);
}
else
{
    while (n > 0)
    {
        n = (long)Math.Ceiling(n / 2.0);
        count++;
        if (n == 1) break;
    }
    sw.Write(count + 1);
}


sw.Flush();
sw.Close();
sr.Close();

 

2. 틀린 코드

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

long n = long.Parse(sr.ReadLine());
int count = 0;

while (n > 0)
{
    if(n % 2 == 0)
    {
        n /= 2;
        count++;
    }
    else
    {
        n--;
        count++;
    }
}

sw.Write(count);
sw.Flush();
sw.Close();
sr.Close();

 

처음에 고양이를 생성하는것 외에는 복제마법이 더 좋기때문에 Math.Ceiling으로 나눌때 소숫점을 올려주어 나눴다.

반례로 50을 입력하면 틀린코드는 8을 출력하는데 맞은 코드는 7을 출력한다.

 

[ 실행화면 ]

case: 2

case: 3

 

 

 

 

---

문제링크: https://www.acmicpc.net/problem/27961

27961번: 고양이는 많을수록 좋다