[파이썬] 이코테 - 그리디 알고리즘, 1이 될 때까지(실전문제)

그리디 알고리즘 (Greedy Algorithm)

• 그리디란 '탐욕'이라는 의미
  즉, 현재 상황에서 지금 당장 좋은 것만 고르는 방법

✔[문제 설명]

• N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램 작성

1. N에서 1을 뺀다.
2. N을 K로 나눈다. (N이 K로 나누어 지는 경우만)

[입력 조건]

• 첫째줄에 N(2 <= N <= 100,000)과 K(2 <= K <= 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이떄 입력으로 주어지는 N은 항상 K보다 크거나 같다.

ex)
25 2 -> 2출력

[내 코드]

n,k = map(int,input().split())
count = 0

while True:
    if n % k==0:
       n = n/k
       count += 1
       
    if n%k!=0:
        n-=1
        count += 1
       
    if n ==1:
        break
    
print(count)

• 처음에 이렇게 코드를 작성했는데 도저히 출력이 안 되는 이유를 알 수가 없었다...............

[답안 예시]

n,k = map(int,input().split())
count = 0

while n>=k:
    
    while n % k!=0:
         n-=1
         count += 1
    n=n//k
    count +=1
        
while n>1:
       n-=1
       count +=1
    
print(count)
        

📌

• 접근 방향은 얼추 똑같았는데 책에 나온 코드에서는 다 while을 이용했다.
• while문에서 n과 k의 관계로 조건을 만들었다.
• n이 k보다 작은 경우에는 무조건 -1을 해야한다는 부분을 캐치하지 못했다.
• 굉장히 쉬운 난이도 문제였는데, 문제를 더 꼼꼼히 분석하고 코딩하자.

@이것이 코딩 테스트다 with 파이썬