2 분 소요

1이 될 때까지

문제

어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행하려고 한다.

단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

  1. N에서 1을 뺀다.
  2. N을 K로 나눈다.

입력조건

  • 첫째 줄에 N(2<= N <= 100,000)과 K(2 <= K <= 100,000)가 공백으로 구분되며 각각 자연수로 주어진다.

    이때, 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력조건

  • 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

입력예시

25 5

출력예시

2

나의 코드

첫 번째 시도.

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

count=0
while True:
    #n이 k의 배수가 아니라면 배수가 될 때까지 -1을 빼준다.
    #연산을 시행하기 전 n=1인지 아닌지 검사를 함.
    if n%k!=0:
        if n==1:
            break
        else:
            n-=1
            count+=1
    #n이 k의 배수이면 n을 k로 나누고 이 값을 다시 n에 할당시켜준다.
    #연산을 시행하기 전 n=1인지 아닌지 검사를 함.
    else:
        if n==1:
            break
        else:
            n=n//k
            count+=1

print(count)

🌝 Thinking

[그리디] (이코테) 큰수의 법칙 문제에서 반복구문을 사용할 때

이를 빠져 나오는 조건을 꼼꼼히 하면 좋다는 것을 알게 되었고, 특별히 while 구문을 빠져나오는 조건을 신경 써 주었다.

답안 예시1

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

result=0
while n>k:
    while n%k!=0:
        n-=1
        result+=1
    n //= k
    result+=1
while n>1:
    n-=1
    result+=1

print(result)

🌝 Thinking

내가 생각했던 것과 큰 틀은 일치하는 듯 함.

나의 코드는 하나의 루프문에서 n이 k로 나누어 질 때 안나누어질때의 경우를 나누어서 한번에 연산을 함.

답안코드는 n이 K보다 클때와 작을때를 나누어서 루프문을 2개로 나누어 연산을 함. n=1일때를 if를 이용하여

각 구문마다 break를 걸어줄 필요가 없음.

🌞 최적해 보장

k가 2이상이기만하면, k로 나누는 것이 1을 빼는 것보다 숫자의 크기의 감소가 크다.

연산의 시행 횟수를 줄이기위해선 나누기 연산을 최대한 많이 사용하여야 한다.

즉 n이 k의 배수가 되었다고하면 무조건 나누어주어야 한다. (최적 해를 보장함)

답안예시2

그런데 여기서 N의 크기가 100억 이상이라면 ?

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

result=0

while True:
    target=(n//k)*k       #검산 공식이라고 생각하면 빠르게 이해가 됌. n//k(몫)*k(나누는 수) = k의 배수
    result += (n-target)     #그 격차만큼을 위에선 한 순회당 -1씩 빼주었지만, 연산 횟수를 줄이기 위하여 바로 빼버림.
    n=target
    
    if n<k:
        break
        
   	n //=k
    result+=1
    
result += (n-1)

print(result)

🌝 Thinking

while 구문을 순회할때 n이 k의 배수에 도달하기위해 우리는 -1씩 빼주는 원리를 이용하여 알고리즘을 짰다. (그리디 알고리즘이니깐 아주 탐욕적으로 원하는 바를 그대로 구현 하는데 집중하였기 때문인가 ?)

하지만 -1빼면 n과 n이 k의 배수가 되는 지점까지의 격차가 매우크다면 whlie 구문이 동작이 많아 질 것이다.

그래서 그냥 그격차만큼을 빼고 result에 그 격차를 그대로 더 해줌. 결과값에 영향을 주지 않음.

💡 깨달은 점.

  1. 알고리즘을 짤 때 과연 내가 짠 알고리즘이 최적해를 보장할 수 있는가 ? 에 대해서 생각해 볼 수 있었다.
  2. 효율적인 알고리즘을 짜기위해선 당연한 원리에 대해서는 비약도 필요하다는 것을 알게 되었다.

출처

이것이 코딩 테스트다 - 나동빈 저

댓글남기기

참고