99클럽 코테 스터디 13일차 TIL: 수학

문제

https://www.acmicpc.net/problem/27961

풀이

이 문제는 최소 행동으로 정확히 N 마리의 고양이를 만드는 문제이다.
문제를 읽어보면 눈치채겠지만, 생성마법 보다 복제마법이 무조건 유리하다.

이는 그리디 알고리즘이라고 할 수 있을 것 같다.

0 -> 1 -> 2 -> 4 -> 8 -> 16 ...

고양이를 최소행동으로 많이 생성하려면 2의 제곱형태로 복제하는 것이 가장 빠르다.

여기서 한가지 패턴을 발견할 수 있다.
현재 고양이가 4마리가 있다고 가정해보자.

4마리에서 7마리를 만드는거나, 8마리를 만드는거나 동일한 횟수 (복제마법) 이 필요하다는 것을 알 수 있다.

4...8, 8...16, 16...32 해당 범위 안으로 고양이를 만드는 것은 동일하다.

수학적으로 보면 $log_{2}N$ 임을 확인할 수 있다.

15와 16을 예시로 들어보자.
$log_{2}15 = 3.xyz, log_{2}16 = 4.0$ 이다.

올림해준다면 둘다 4로 동일하다.

이제 1 -> N으로 가는 횟수는 $log_{2}$를 통해 구할 수 있다는 것을 알았다.
0 -> 1로 가는 마법의 횟수는 1이므로 결론적으로는 $log_{2}N$을 올림하고 거기에 +1을 해주면 정답을 유추할 수 있다.

한 가지 예외상황이 있다면 N이 0일 때이다. 이때는 그냥 0을 출력하자.

소스코드

후기

패턴을 발견하고 수식을 떠올린다면 쉽게 풀 수 있는 문제이다.
Swift에 log를 사용할 수 있어서 편하게 풀었다.