[항해99] 99클럽 코테 스터디 13일차 TIL + 백준 27961

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

오늘의 학습 키워드

• 백준 27961
• 고양이는 많을수록 좋다
• 그리디 알고리즘

공부한 내용

# 백준 27961
# 고양이는 많을수록 좋다

import sys
input = sys.stdin.readline  

N = int(input())  # 목표 고양이 수
cat = 1          # 현재 고양이 수 (첫 번째 고양이 생성 가정)
count = 0        # 행동 횟수

# 특수 케이스 처리
if N == 0:      # 고양이가 필요 없는 경우
    print(0)
elif N == 1:    # 고양이 1마리만 필요한 경우
    print(1)
else:
    while cat != N:  # 현재 고양이 수가 목표와 다른 동안 반복
        # 남은 필요한 고양이 수(N - cat)가 현재 고양이 수(cat) 이하인 경우
        if cat >= N - cat:
            cat += N - cat  # 필요한 만큼만 추가
            count += 1
        # 현재 고양이 수를 모두 복제해도 괜찮은 경우
        else:
            cat += cat      # 현재 수만큼 복제
            count += 1
    print(count + 1)  # 첫 번째 고양이 생성 횟수를 더해줌

• 0마리와 1마리는 특수한 케이스니 바로 처리할 수 있도록 구현
• 현재 고양이 수에서 시작하여 목표치까지 도달하는 접근
• 매 단계에서 남은 고양이 수가 현재 수보다 작거나 같으면, 정확히 그만큼 생성 하고 그렇지 않으면 현재 수만큼 복제

오늘의 회고

• 처음에는 N에서 0으로 가는 방식으로 접근

  import sys
  input = sys.stdin.readline
  

N = int(input())
count = 0

while N != 0:
if N % 2 == 0:
N //= 2
count += 1
else:
N -= 1
count += 1

print(count)

- 이런 방식은 복제의 특성을 제대로 반영하지 못하고, 실제 마법의 사용 순서와도 다름
- 문제를 해결할 대 접근 방식을 전환하는 유연한 풀이 방식이 중요