[이것이 코딩테스트다] 그리디 - 1이 될때까지 문제풀이

문제

어떤수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고한다. 단, 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

 

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

 

예를 들어 N = 17, K = 4일 경우

1) 17 - 1 = 16

2) 16 // 4 = 4

3) 4 // 4 = 1

 

전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다. 

 

 

 

 

나의 코드

# 1) N에서 1을 뺀다
# 2) N을 k로 나눈다.

# 1) N/K 가 나누어 떨어지는 경우 나눗셈 실행 (우선실행해야 횟수를 최소한으로 할 수 있다.)
# 2) 나누어떨어지지 않은 경우 -1 실행

N = 17
K = 4

count = 0

while N != 1:
    if N % K != 0:
        N = N - 1
        count += 1

    else:
        N = N / K
        count += 1


print(count)

 

나는 while 문을 사용하여 N이 1이 될때까지 반복문을 실행했다. 반복문을 실행하면서 N이 K와 나누어떨어지면 K로 나누고, K와 나누어떨어지지 않으면 -1을 하여 count는 횟수만큼 +1을 해주고 N은 계산 결과로 저장된다.

 

 

 

 

정답 코드

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
    # n을 k로 나눈 몫에 k를 다시 곱한다 -> n이 k로 나눠떨어지지 않을때 가장 가까운 나눠 떨어지는 수를 구할 수 있다.
    target = (n // k) * k
    # 총 연산을 수행하는 횟수 (result) - target 은 1을 처리한 개수를 한번에 구한 것이다.
    result += (n - target)
    n = target

    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break

    # K로 나누기
    result += 1  # k를 나누는 연산을 수행하므로 1번 추가
    n //= k

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

print(result)

출처: github.com/ndb796/python-for-coding-test/blob/master/

 

 

 

 

 

문제풀이

 

(1) 설명

target = (n // k) * k

 

우리는 N이 K로 나누어떨어지는 수가 될때까지 -1을 해야한다. 위에 '나의 코드'에서도 동일하다. 위 식을 통하여 target 이라는 변수에는 N이 K로 나누어떨어지는 가장 가까운 수를 저장한다. 

 

n이 17이고 k가 4일 경우 (17 // 4) * 4 = 16이 된다. K(=4)로 나누어떨어지는 가장 가까운 수가 구해졌다.

 

 

(2) 설명

result += (n - target)

 

result 는 총 연산 횟수를 저장하는 변수이다. 우리는 위에서 target 이라는 K로 나누어떨어지는 가장 가까운 수를 추출했다. 그러므로 (n - target)을 수행하게되면 -1을 수행한 횟수를 구할 수 있다. 

 

 

(3) 설명

n = target

 

target 을 n에 저장한다. 이유는 위에서 설명했듯이, -1 를 수행한 이후 K로 나누어떨어지는 가장 가까운 수인 N이기 떄문이다.

 

 

(4) 설명

if n < k:
	break

 

n 이 k 보다 작아진다면 더이상 연산을 수행할 수 없으므로 반복문을 탈출한다.

 

 

(5) 설명

result += 1  # k를 나누는 연산을 수행하므로 1번 추가
n //= k

 

현재 N은 K로 나누어떨어지는 수가 되었다. 그러므로 연산 횟수를 1번 추가하고 N을 K로 나눈다.

 

 

(6) 설명

result += (n - 1)

 

반복문 탈출 후, 마지막으로 실행된느 코드이다. 우리는 반복문을 n이 k보다 작아졌을 경우 탈출했다. n이 k로 더이상 나눌 수 없기 때문이다. 그러므로 n은 아직 1이 아니다. n이 만약 현재 3이라면 최종 연산 횟수에 2를 더해야한다. (3 - 1 = 2, 2 - 1 = 1)