99클럽 코테 스터디 13일차 TIL / 그리디

✏️ 문제

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

 

마법소녀인 마도카는 너무나도 고양이를 좋아하는 나머지 마법을 이용하여 고양이 N마리를 집에서 키우기로 결심했다!

마도카는 한 번의 행동에서 다음 2$2$가지 마법 중 하나를 선택하여 사용한다. 처음에는 마도카의 집에 고양이가 존재하지 않는다.

 

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

 

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

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 B1

✅ 소요 시간: 42분

✅ 권장 시간: 1시간 15분

 

💡 풀이

1) 문제 유형 파악

처음에는 N의 입력 범위가 10의 12승까지길래 음 이분탐색? 했는데 어떻게 써먹어야 할지 떠오르지 않았다.

 

다음으로 떠올린 방법은 패턴이 있는지 찾는 것이었다. N=0~N=20까지 직접 적어가면서 확인해보니까 패턴이 있긴 했는데 내 머리로는 일반화 시킬 방법이 보이지 않았기 때문에 이 방법도 일단 패스!

 

마지막으로 문제를 다시 읽어보니까 복제를 최대한 많이 써야겠다 싶은 생각이 들었다. 이런 패턴은 그리디 문제(like 동전 문제)에서 많이 봤던 것 같아서 그리디 유형으로 분류하고 나눗셈을 잘 활용하는 방향으로 문제를 풀어보기로 했다.

 

2) 아이디어 흐름

① 현재 고양이 수, 연산 횟수 저장용 변수 선언

문제대로라면 초기 고양이 수는 0마리, 연산 횟수도 0번이지만 N이 0인 경우를 제외하고 한 마리를 추가하는 생성 과정이 무조건 필요하기 때문에 현재 고양이 수와 연산 횟수 모두 초기값을 1로 줬다.

 

② 현재 고양이 수와 N 비교

목표는 더도 말고 덜도 말고 정확히 N마리를 만드는 것이므로 현재 고양이 수가 N과 같아지기 전까지만 while문을 돌려주면 된다.

 

while문 안에서는 딱 한 마리만 추가되는 생성 과정은 고려할 필요가 없고 현재 고양이 수의 2배까지 늘릴 수 있는 복제 과정만 신경쓰면 되기 때문에 현재 고양이 수 *= 2와 연산 횟수 += 1을 계속 수행해주면 풀이 끝

 

③ 예외 처리

①에서 언급했듯이 N=0이면 생성 과정이 필요없다. if문을 이용해서 N == 0이면 바로 0 출력, N != 0이면 ①, ② 순서대로 처리되게 코드를 짰다.

 

사실 처음에 예외 처리를 안 해서 틀렸습니다 한 번 만났다 껄 껄

 

3) 구현

import sys

input = sys.stdin.readline

N = int(input())

if N == 0:
    print(0)
else:
    cats = 1

    answer = 1

    while cats < N:
        cats *= 2
        answer += 1

    print(answer)

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 오늘은 어려웠던 점보다 아쉬운 점이라고 하는 게 맞겠다. 풀고 보니까 코드는 엄청 간단한데 '나눗셈을 잘 쓰는 것' 이걸 바로 떠올리지 못해서 브론즈 문제 치고 시간을 너무 많이 쓴 게 아쉽다.

❗ 배운 점

• 코드 다 짜고 나서 예외가 있을지 한 번 더 생각하는 습관을 가지자.