그리디 알고리즘(탐욕법) - [문제]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(1<= N <= 100,000)과 K(2<= K <= 100,000)가 공백을 기준으로 하여 각각 자연수로 주어집니다.

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

문제 해결 아이디어

• 주어진 N에 대하여 나눌 수 있는 수라면 최대한 많이 나누기를 수행하면 된다.
• N의 값을 줄일 때 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 훨씬 많이 줄일 수 있다.

정당성 분석

• 가능한 최대한 많이 나누는 작업이 최적의 해를 항상 보장할 수 있을까?
• N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있다
• 다시 말해 K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있다.
• 또한 N은 항상 1에 도달하게 된다. (최적의 해 성립)

내가 작성한 코드 - Javascript

function untilYouReachOne(n,k){

  let count = 0;

  while(true){

    let target = Math.floor(n/k)*k;

    count += n-target;

    n = target;

   

    if(n < k)

      break;

   

    n = n/k;

    count++;

  }

  count= count+(n-1);

 

  return count;

}



console.log(untilYouReachOne(100,7));

 

이 문제같은 경우는 n과 k가 10만 이하의 정수이기 때문에 이렇게 작성하지 않고 매번 n을 확인해서 n이 k로 나누어떨어진다면 나눠주고 그렇지 않다면 1을 빼주고 이런식으로 간단하게도 작성할 수 있다. 그러나 이렇게 코드를 작성하면 이 반복문이 한 번 반복이 될 때마다 바로 n이 k로 나누어지는 연산이 수행이 되기 때문에 반복횟수에 따라서 기하급수적으로 n이 빠르게 줄어들게 된다. 즉, 시간복잡도가 "로그시간복잡도"가 나올 수 있다. 우리의 코드가 더 빨리 실행될 수 있도록 이렇게 작성했다고 보면 된다.