[Python] 이것이 코딩테스트다 with 파이썬 - 그리디 - 1이 될 때 까지

* 해당 문제 및 해설은 "이것이 코딩 테스트 다 with 파이썬" 책을 기준으로 요약 및 정리 하여 작성하였습니다.  

 

http://www.yes24.com/product/goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

---

그리디 알고리즘이란 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 을 의미한다. 
그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

문제 설명 : 그리디 - 1이 될 때 까지

어떠한 수 N 이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번째 연산은 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 를 공백으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
	# (N == K 로 나누어떨어지는 수)가 될 때까지 1씩 빼기
    target = (n//k) * k
    result += (n - target)
    n = target
    
    # N 이 K 보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
    	break
    # K로 나누기
    result += 1
    n //= K

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n-1)

print(result)

 

 

개인적인 생각

그리디 알고리즘 경우에는 항상 속도를 줄이는 것에 목표를 두어야 한다. (효율성을 높이는 방식으로 코딩)
입력 받는 값의 범위를 파악하고, 범위가 크다면 효율적으로 코드를 작성하는 방향으로 나아가야 한다.

 

오늘의 개발자 명언

소프트웨어 산업의 가장 놀라운 성과는하드웨어 산업이 꾸준히 이루고 있는 성과들을 착실하게 갉아 먹고 있다는 것이다.
(Henry Petroski, 실패 분석으로 유명한 엔지니어)

출처 : 프로그래밍에 관한 명언 101가지