[99클럽 코테 스터디 TIL 16일차 / 백준 27961] 고양이는 많을수록 좋다 (Python)

 

처음에 문제를 읽고 BFS로 코드를 작성하였다.

 

그런데 예제 입력3에서 출력 값이 안나왔다 ... 아무래도 BFS 알고리즘으로 풀면 쓸데 없이 탐색하는 값이 너무 많아서 출력이 안나오는 것 같다.

 

그래서 간단히 다시 코드를 작성해보았다.

 

내 코드

n = int(input())
t = 1
cnt = 1

if n == 0: print(0)
elif n == 1 : print(1)
else:
    while t != n:
        if n - t <= t:
            print(cnt + 1)
            break
        else:
            t += t
            cnt += 1

일단 N 값이 0이거나 1이면 횟수도 0, 1이기 때문에 바로 출력해주었고 0 또는 1이 아닌 경우엔 처음엔 무조건 +1을 해야 t = 1, cnt = 1로 초기화해준다. 여기서 t는 현재 고양이 수이다.

 

1. t == n이 될때까지 while문을 돌려준다

2. n - t <=  t 인 경우엔 방법 2 마법을 한번만 쓰면 t == n이 되기 때문에 cnt + 1을 출력해준다.

3. n - t > t 인 경우엔 방법 2 마법을 사용해도 아직 n보다 고양이 수가 적기 때문에 방법 2 마법을 사용해 t += t로 업데이트 해주고 cnt += 1을 해준다.

 

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