[이코테 2021] 13강 문제 '1이 될 때까지'

문제

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

1. N에서 1을 뺍니다.

2. N을 K로 나눕니다.

 

예를 들어 N이 17, K가 4라고 가정합시다. 이때 1번의 과정을 한 번 수행하면 N은 16이 됩니다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 됩니다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됩니다. 이는 N을 1로 만드는 최소 횟수입니다.

 

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하세요.

 

문제 조건

풀이 시간 15분, 시간 제한 2초, 메모리 제한 128MB

 

입력

첫째 줄에 N과 K가 공백을 기준으로 하여 각각 자연수로 주어집니다.

 

출력

첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력합니다.

---

'문제 풀기 위한 최소한의 아이디어'

주어진 N에 대해 최대한 많이 나누기를 수행하면 최적의 해를 구할 수 있다.

-> 정당성 분석 : N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있음. 즉, K가 2 이상이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있음. 따라서 최적의 해 성립!

 

'정답 코드'

1) 이코테 강의 정답 코드

# 그리디 알고리즘
N, K = map(int, input().split())

cnt = 0

while 1: 
  # N이 K로 나눠지지 않을 때 K로 나눠떨어지는 가장 가까운 
  num = (N // K) * K 

  # 1을 빼는 연산의 수
  cnt += (N - num)

  N = num

  # 더이상 나눌 수 없을 때 반복문 탈출
  if N < K :
    break;

  # K로 나누기
  N = N // K
  cnt += 1

# 마지막으로 N이 1보다 크다면 1을 만들어줘야 함
cnt += (N - 1)
print(cnt)

https://youtu.be/2zjoKjt97vQ 링크 참고

 

2) 내가 작성한 코드

# 그리디 알고리즘
N, K = map(int, input().split())

cnt = 0

while 1: 
  num = N % K

  for i in range(num):
    if N == 1 :
      break
    N -= 1
    cnt += 1

  if N == 1 :
    break
    
  else :
    N = N // K
    cnt += 1

print(cnt)

처음엔 for문 안에 if문으로 N이 1일 때 break해주지 않아 CPU 타임 초과가 떴다.

다음부터는 로직 짤 때 주의하자!