[99클럽 5기] 코딩테스트 스터디 16일차 TIL - 그리디 알고리즘

[Bronze I] 고양이는 많을수록 좋다 - 27961 

[문제 링크](https://www.acmicpc.net/problem/27961)

🗝️오늘의 학습 키워드 (Keyword)

• 그리디 알고리즘

---

💻본인의 언어로 내용 정리 (Today I Learned)

생성 마법과 복제 마법을 적절히 사용하여 입력받은 수 만큼의 고양이를 만드는 프로그램을 작성하는 문제이다.

 

테스트 케이스에서, 6을 입력 받았을 때 초기 0마리 -> 생성 1마리 -> 생성(복제) 2마리 -> 복제 4마리 -> 복제 6마리로 총 4번의 마법을 사용하였다.

 

복제 마법에 힌트가 숨어있다. k마리의 고양이가 존재할 경우, 복제 마법을 통해 0 ~ k 마리의 고양이를 추가할 수 있다고 한다. 복제 4마리에서 복제 6마리로 넘어갈 때, 정확하게는 4 ~ 8마리 까지 가능하다는 것이다.

 

2의 배수로 넘어갈 때만 마법의 횟수가 하나 증가한다고 생각하고 알고리즘을 설계해보았다.

이런 식의 범위를 가지게 될 것이다.

💡알고리즘 풀이

def cat(N):
    magic_count = 0 # 마법 사용 횟수
    cat_num = 1 # 고양이 수(처음엔 무조건 생성이기에 1마리에서 시작)
    
    while (N > cat_num): # 고양이를 2배 복제하면서, 범위 내에 존재할 경우 stop
        cat_num *= 2
        magic_count += 1

    return magic_count + 1 if N <= cat_num else magic_count + 1 # 복제 횟수 + 처음 생성 횟수

N이 2의 배수보다 작아질 때 까지 반복을 돌려 복제 마법 횟수를 카운트 한다. 6일 경우, 4보단 크고 8보단 작기 때문에 카운트 횟수는 3회가 될 것이고, 초기에는 무조건 고양이 생성 마법을 사용하기에 리턴에 +1을 한다.

 

🗒️제출 코드

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

import sys
input = sys.stdin.readline

N = int(input())

def cat(N):
    magic_count = 0 # 마법 사용 횟수
    cat_num = 1 # 고양이 수(처음엔 무조건 생성이기에 1마리에서 시작)
    
    while (N > cat_num): # 고양이를 2배 복제하면서, 범위 내에 존재할 경우 stop
        cat_num *= 2
        magic_count += 1

    return magic_count + 1 if N <= cat_num else magic_count + 1 # 복제 횟수 + 처음 생성 횟수

print(cat(N) if N != 0 else 0)

---

💭오늘의 회고

4주차의 시작 문제이다. 이번 주차는 그리디 알고리즘에 대해 공부하는 차시인 것 같다.

알고리즘을 공부하며 유독 그리디가 좀 부족하다 생각하였는데, 이번 주차에 열심히 공부해봐야 겠다는 생각을 하였다.

 

벌써 4주차라니, 이제 99클럽과 함께할 날이 2주도 남지 않았다. 남은 기간동안 조금 더 열심히 해서 유종의 미를 거두어 보자.

---

⬇️전체 소스코드⬇️

hanghae99/python_middler/16일차 고양이는 많을수록 좋다/고양이는 많을수록 좋다.py at main · Do-h