99클럽 코테 스터디 4기 13일차 TIL - 백준: 고양이는 많을수록 좋다(27961) Swift & Python

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	27961	고양이는 많을수록 좋다	그리디	브론즈1	Swift, Python

🚀 나의 접근 방법

최소의 행동 횟수를 구해야 하기 때문에 가능한 한 행동에 고양이를 가장 많게(욕심적이게) 해야 한다. 즉, 그리디 알고리즘을 사용하면 된다.

복제 마법 설명에 "0마리 이상 k마리 이하의 고양이를 마도카의 집에 추가할 수 있다." 라는 것이 있지만 이것에 속으면 안 된다. 결국 2배씩 고양이를 늘려나간다고 생각하면 된다.

처음에는 고양이가 0마리이기 때문에 생성 마법으로 한 마리 생성한다. 그 이후로는 복제 마법으로 고양이 수를 N 보다 크거나 같을 때까지 2배 하면 된다.

그러면 아래와 같이 총 4번의 행동으로 N(6) 보다 커지게 된다.

0 > 1 > 2 > 4 > 8 (이지만 이전 4에서 2마리를 복제했다 생각하면 됨)

그런데 마지막 값이 기대했던 6이 아닌 8이지 않은가? 그러면 우리는 단순히 마지막 복제 행동을 4에서 2마리를 복제했다 생각하면 된다.

즉, 2마리를 복제하나 4마리를 복제하나 결국 행동은 1번이라서 상관없다는 것이다. N 보다 크거나 같게만 해주면 문제가 해결된 것이다.

✍️ 나의 코드

Swift

let N = Int(readLine()!)!
var n = 0
var result = 0

while N > n {
    if n == 0 {
        n += 1
    } else {
        n *= 2
    }
    result += 1
}

print(result)

Python

N = int(input())
n = 0
result = 0

while N > n:
    if n == 0:
        n += 1
    else:
        n *= 2
    result += 1

print(result)

🤔 회고 및 개선사항

다양한 문제를 자주 풀어보자

오랜만에 그리디 문제를 풀어보았는데 어렵지 않은 문제임에도 불구하고 빠르게 해결하지 못했다. 아무래도 요즘에 탐색 위주로 문제를 풀다 보니 다른 알고리즘의 감이 떨어진 것 같다. 다양한 유형의 문제를 적적히 섞어 풀어 보는 것이 좋을 것 같다.