[코딩테스트 python] 그리디 Greedy; 1이 될 때까지

 

#저서 : 이것이 취업을 위한 코딩테스트다 with 파이썬

#기출 : 2018 E 기업 알고리즘 대회

 

# 문제

N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택 수행할 때, N이 1이 될때까지 1번 혹은 2번의 과정을 수행해야하는 쵯솟값 출력

1. N에서 1을 뺀다
2. N을 K로 나눈다 (단, N이 K로 나누어떨어질 때만 선택)

# 제한사항

• 첫 줄 : N(2<=N<=100,000)과 K(2<=K<=100,000) 공백으로 구분. 자연수. 항상 N >= K

 

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

cnt = 0
while n!=1:
  if n%k==0:
    n = n//k
    cnt += 1
  else:
    n -= 1
    cnt += 1
print(cnt)

> 단순하게 조건문으로 나누어 떨어지면 나누고 아니면 1을 빼는 식으로 해결

>> 단점 : 만약 N이 100억 이상이라면 시간 효율↓  > N이 K의 배수가 되도록 한 번에 빼는 것이 효율적

# 책의 답안 예시
n, k = map(int, input().split())

cnt = 0
while True:
  target = (n//k) * k  #k의 배수 확인
  
  cnt += (n-target) #배수가 될 때까지 한번에 1을 빼기
  n = target        #이미 배수가 될 때까지 뺐으니 n에 저장
  
  if n < k: #더이상 나눌 수 없으면 종료
    break
	
  n //= k   #n을 k의 배수로 나눔
  cnt += 1  #위에서 한번 n을 k로 나눴으니 1회 카운트
  
print(cnt)

>> 생각보다 시간복잡도까지 생각해서 코드를 짜는 것이 어려움.
>> 다음에는 한번에 작업할 수 있는 것이 더 있을 까를 생각해보는 연습이 필요할 듯!