99클럽 코테 스터디 _ 16일차 TIL (그리디)

 

< 문제 >

[백준] 27961. 고양이는 많을수록 좋다 / 브론즈1

---

< 풀이 >

코드 변수 정의

• cnt : 연산 횟수
• madoka_cat : 현재 고양이 수

---

Greedy
시간복잡도 : O(logN)

def f():
    N = int(input())
    cnt, madoka_cat = 0, 0 # 연산 횟수(cnt)와 현재 고양이 수(madoka_cat) 초기화
    while madoka_cat < N: # 목표 N에 도달할 때까지 반복
        # +1 연산과 *2 연산 중 더 큰 값을 선택하되, N을 초과하지 않도록 min 사용
        madoka_cat = min(N, max(madoka_cat + 1, madoka_cat * 2))
        cnt += 1 # 연산 횟수 증가
    return cnt

print(f())

 

 

 

풀이 방식

 

고양이 수를 증가시키는 과정에서 최소한의 연산 횟수를 찾는 문제로, 고양이 수 madoka_cat은 두 가지 방법으로 증가할 수 있다.

1. 생성 마법    →     +1 연산
2. 복제 마법    →     x2 연산
   • 마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다.
   • 0마리 이상 k마리 이하의 고양이를 추가할 수 있으므로 고양이 수를 최대 2배까지 늘릴 수 있다.

 

 

while문 :

• 초기 madoka_cat = 0으로 시작하여 N에 도달할 때까지 최소한의 연산을 수행한다.
• x2 연산을 최대한 활용하는 것이 빠르게 증가하는 방법이므로, 매번 max(madoka_cat + 1, madoka_cat * 2)를 선택한다.
  • madoka_cat + 1과 madoka_cat * 2 중 더 효율적인 증가 방법을 선택.
• 단, N을 초과하지 않도록 min(N, max(...))을 사용한다.

 

 

예시 ) N = 10

반복 횟수(cnt)	이전 madoka_cat	madoka_cat + 1	madoka_cat * 2	선택된 madoka_cat
1	0	1	0	1
2	1	2	2	2
3	2	3	4	4
4	4	5	8	8
5	8	9	16 → 제한	10 (N 도달)

---

< 회고 >

🤔 💭_

처음에는 if문을 써서 madoka_cnt + 1과 madoka_cnt * 2를 비교하여 더 큰 값을 갖는 경우 madoka_cnt 값을 증가시키는 방법으로 구현했다.

• madoka_cnt + 1  >  madoka_cnt * 2인 경우   →    고양이 1마리를 추가한다.
• madoka_cnt + 1 <= madoka_cnt * 2인 경우   →   k(madoka_cnt) 마리 이하의 고양이 중 N을 넘지 않을 고양이 수를 추가한다.

근데 굳이 조건문을 쓸 필요 없이 max로 madoka_cnt + 1(생성 마법)과 madoka_cnt * 2(복제 마법) 중 더 큰 값을 선택한다. madoka_cnt * 2가  max값으로 선택된 경우, N을 넘는 수가 나올 수 있지만 복제마법은 0~k이하의 값을 가지기 때문에 madoka_cnt가 N이 되는 수를 포함하고 있으므로 그냥 madoka_cnt * 2로 반환한 후 min 값으로 최종적으로 madoka_cnt가 N 값을 가질 수 있도록 한다.