[백준 알고리즘] 27961번: 고양이는 많을수록 좋다 (Python)

Algorithm/백준

에릭 Kim 2023. 7. 4. 16:48

27961번: 고양이는 많을수록 좋다

올바른 행동 순서가 될 수 있는 하나의 예시는 아래와 같으며, $4$번보다 더 작은 행동 횟수로 $6$마리의 고양이를 마도카의 집에 들이는 것은 불가능하다. 초기 상태($0$마리) $\rightarrow$ 생성

www.acmicpc.net

★ 시작할 때 고양이 0마리부터 시작하기 때문에 고양이를 1마리로 증가시킬 때만 생성마법을 사용하고, 그 이후에는 복제 마법을 사용하는 것이 효율이 좋습니다 !

★ 고양이의 수가 n과 같아질 때까지 반복문을 수행하는데, 만약 n - t가 현재 고양이 수보다 크면 자기 자신만 복제하고, 반대의 경우에는 n-t만큼 복제해야 합니다.

ex) n = 7

첫 반복문

t = 1

n - t = 6

=> t = 2, cnt = 1

두번째 반복문

t = 2

n - t = 5

=> t = 4, cnt = 2

세번째 반복문

t = 4

n - t = 3

=> t = 7, cnt = 3

★ 출력할 때 cnt에 +1을 해주는 이유는 고양이의 수를 0마리에서 1마리로 만들 때 생성마법을 한번 사용했기 때문입니다.