그리디 알고리즘 - 1이 될 때 까지

문제 설명

• 어떠한 수 N이 1이 될 때 까지 다음 두 과정중 하나를 반복적으로 선택하여 수행하려고 한다. 
• N에서 1을 뺀다
• N을 K로 나눈다(단, N이 K로 나누어 떨어질 때만 선택 가능)

문제 조건

• 첫째줄에 N(2 ≤ N ≤100000)과 K(2 ≤ K ≤ 100000)가 공백으로 구분되며 각각 자연수로 주어진다. 
• N은 항상 K보다 크거나 같다

입력 예시

• 25 5

• 출력 : 2

NxM 배열 형태로 놓여있는 카드들을 각 행별로 하나씩 골라 가장 큰 수를 찾는 문제이다. 단, 각 행에서 가장 작은 수를 골라야 한다. 

• 아이디어 : 각 행별로 최솟값들을 모은 뒤, 그 중에서 최댓값을 구함
• 최솟값 = Math.min()
• 최댓값 = Math.max

나의 답안

let answer = 0
let [n, K] = prompt().split(" ")
while(n > 1){
    //n이 1이 될 때 까지 반복
    if(n % k != 0){
      //n이 k로 나누어 떨어지지 않는다면
      n--
      //n에서 1을 뺌
      answer++
      //횟수 증가
    } else{
      //n이 k로 나누어 떨어진다면
      n /= k
      //n을 k로 나눔
      answer++
      //횟수 증가
    }
  }

실행 결과

정당성

뺴기보다 나누기가 수를 줄이는데 효과적이다. 따라서 최대한 나누기를 많이 하는 것이 실행 횟수를 줄이는데 도움이 될 것이다. N에서 1씩 빼서 K의 배수로 만들고, K의 배수가 되면 바로 K로 나누어 버리면 된다.