반응형
https://www.acmicpc.net/problem/27961
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마리로 만들 때 생성마법을 한번 사용했기 때문입니다.
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 18238번: ZOAC 2 (Python) (0) | 2023.07.05 |
|---|---|
| [백준 알고리즘] 4963번: 섬의 개수 (DFS, Python) (0) | 2023.07.05 |
| [백준 알고리즘] 4889번: 안정적인 문자열 (Python) (0) | 2023.07.03 |
| [백준 알고리즘] 1012번: 유기농 배추(DFS, Python) (0) | 2023.07.03 |
| [백준 알고리즘] 1817번: 짐 챙기는 숌 (Python) (0) | 2023.06.29 |