[99클럽 코테 스터디 13일차 TIL] 고양이는 많을수록 좋다 - 백준 27961

13일만에 세번째 키워드가 등장했다. Greedy!

 

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

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

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

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

[입력]
첫 번째 줄에 키우기를 원하는 고양이의 수 N(0 ≤ N ≤ 10^12)이 정수로 주어진다.

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

풀이 접근

맞는 말이다. 고양이는 많을수록 좋다. ㅎㅎ

최초에는 생성 마법을 반드시 사용해야한다.

이후에는 있는 고양이를 복제해가면서 수를 늘린다.

고양이의 수는 2배씩 증가할 것이고, N마리가 넘기 직전에만 적절한 수의 고양이를 복제하면 된다.

let n = Int(readLine()!)!
var cat = 1
var magicCount = 1
while cat < n {
    cat *= 2
    magicCount += 1
}

고양이 수의 범위가 0부터 시작되기 때문에 0마리의 고양이가 필요할 경우를 대비해서 결과를 출력한다.

print(n == 0 ? 0 : magicCount)

최종 코드 - Swift

let n = Int(readLine()!)!
var cat = 1
var magicCount = 1
while cat < n {
    cat *= 2
    magicCount += 1
}
print(n == 0 ? 0 : magicCount)

최종 코드 - Python3

Swift랑 똑같다.

n = int(input())
cat = 1
magicCount = 1
while cat < n:
  cat *= 2
  magicCount += 1
print(0 if n == 0 else magicCount)

Conclusion

굉장히 쉬웠다. 커뮤니티를 보니 다른 분들도 쉬웠던 모양이다.