[코테] 그리디 문제풀기 - 1이 될 때까지

Day4

그리디 문제풀기 - 1이 될 때까지 (2018 E 기업 알고리즘 대회 기출 / 난이도 하)

 

<문제>

N이 1이 될 때까지 2개의 과정 중 하나를 반복해서 수행하고, 과정 수행의 최소 횟수를 출력해야 한다. 단, 2번 과정은 N이 K로 나누어떨어질 때만 수행할 수 있다.

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

 

<조건>

첫째 줄 : N(2≤N≤100,000), M(2≤k≤100,000) 자연수 입력. 공백 구분

N은 항상 K보다 크거나 같다.

1이 될 때까지 풀이 

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

cnt = 0

while True:
  #n이 1이 되면 반복문 중단
  if n == 1:
    break
  #n이 1이 아닌 경우
  else:
    #n이 k로 나누어 떨어지면 나눗셈 진행
    if n % k == 0:
      n /= k
      cnt += 1
    #n이 k로 나누어 떨어지지 않으면 뺄셈 진행
    else:
      n -= 1
      cnt += 1
  
print(cnt)

n이 1이 될 때까지 while 반복문을 돌리고, n이 k로 나누어 떨어지면 나눗셈을 하고 나누어 떨어지지 않으면 1을 뺀다. 1이 될 때까지 나누거나 빼는 연산을 최소 횟수로 반복해야하는데 뺄셈보다 나눗셈이 1회에 더 작은 수로 만들어줄 수 있으므로 최대한 나눗셈을 많이 하는 것이 좋다. 

+ while문에 True를 조건으로 두는 대신에 n != 1를 조건으로 둘 수도 있을 것이다. 그런데 n이 100억 이상의 큰 수가 된다면 더 효율적으로 코딩을 해야 한다고 한다..!

 

 

#솔루션 「이것이 코딩 테스트다」 p.102

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

while True:
  target = (n // k) * k
  result += (n - target)
  n = target
  if n < k:
    break
  result += 1
  n //= k
  
result += (n - 1)
print(result)