[그리디] 1이 될 때까지

[문제]

- 숫자 N, K 가 주어진다.

- N에 대하여 다음 두가지 연산을 할 수 있다.

  a. N-1

  b. N/K (떨어질때만 가능)

- a,b 연산을 이용하여 N을 1로 만들수있는 최소횟수를 만들어본다.

- N=17, K=4 라면, a, b, b 연산으로 1을 만들 수 있다. 

 

[아이디어]

- 1을 만들기위해서는 a 보다 b 가 유리하다. 

- 큰수에서는 당연하다. 작은수에서 검증을 해보면, N=2 일때 a 와 b 의 효력이 같아진다.

- 결국 나눌수있다면 나누고, 나눌수 없다면 빼는 식으로 간다.

 

[실패코드]

n = 10000
k = 4
result = 0 

# n 이 1보다 크다면 연산을 계속한다. 
while( n > 1 ):
# n 이 k 로 나누어떨어지지않는다면, n에서 1을 빼준다.
  while (n%k != 0):
    n -= 1
    result += 1
# n 이 k 로 나누어떨어진다면 (위 반복문을 나온다면)
  if (n%k == 0):
    n = n//k
    result += 1

print(n)
print(result)

- 단순하게 위와 같이 코드를 짜보았다. 

- 위 코드를 돌려본결과, 간과한 사실이 있었다. 

- 위 코드는 나눌수있을때까지 n을 (-1) 시키고, 나눌수있게되면 n을 (/k) 시킨다.

- 즉, k보다 작은숫자로 반복문의 시작부분을가게되면, k=4 일때 3, 2, 1, 0 으로 0을 만들어버리게된다. 

 

[개선코드]

n = 128
k = 4
result = 0 

# n 이 1보다 크다면 연산을 계속한다. 
while( n > 1 ):
# n 이 k 로 나누어떨어지지않는다면, n에서 1을 빼준다.
  while (n%k != 0):
    n -= 1
    result += 1
    if( n == 1 ):
      break
# n 이 k 로 나누어떨어진다면 (위 반복문을 나온다면)
  if (n%k == 0):
    n = n//k
    result += 1

print(n)
print(result)

- 따라서 이렇게 중간에 n==1 일때 빠져나올수 있는 구문을 넣어주었다.

 

[문제해설]

 

- 책에서는 또다른 방법을 제안하고있다. 

- n이 k보다 크다면, 계속해서 나누기위한 연산을 진행한다.

- n이 k보다 작아지는 순간에는, -1 로 '1' 을 만들어간다.

 

n = 128
k = 4
result = 0 

# n >= k 인 경우
while (n >= k):
  if(n % k != 0):
    n -= 1
    result += 1

  if(n % k == 0):
    n /= k
    result += 1

# n < k 인 경우
while (n > 1):
  n -= 1
  result += 1

print(n)
print(k)

 

- 책과 완전히 동일하게 작성하진 않았지만, 내가 좋아하는 스타일로 수정하였다.

- 온전히 내가 작성했던 코드보다 좀더 깔끔하긴하다. 사실 0이 나올 가능성을 나중에서야 알게되었으며, 개선방법을 찾는데도 살짝 혼란스러웠다.

- n이 k보다 클때는 나누기에 초점으로 맞추고, 더이상 k로 나눌수 없는경우 (n<k) 를 또다른 케이스로 만들어 코드를 짜니 더 이뻐보였다.