[Algorithm] 그리디 알고리즘 문제 풀이 - 1이 될 때까지

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

 

 

'이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책을 공부 중입니다. 이 글은 해당 책에서 그리디 알고리즘 문제 중 '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번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성하시오.

 

🎁입력 조건

 

첫째줄에 N(2 <= N < = 100000)과 K(2 <= K < = 100000)가 공백으로 구분되며 각각 자연수로 주어진다.

 

🎊출력 조건

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

 

🎁입력 예시

25 5

 

🎊출력 예시 

2

 

문제 해설

 

문제를 해결하기 위한 아디이어는 ‘최대한 많이 나누기’를 하는 것이다. 어떠한 수가 있을 때 ‘2 이상의 수로 나누는 것’이 ‘1을 빼는 것’보다 숫자를 훨씬 많이 줄일 수 있기 때문이다. 

 

문제에서는 K가 2 이상의 자연수이므로, 가능하면 나누는 것이 항상 더 숫자를 빠르게 줄이는 방법이 된다.

 

아래는 최초로 작성한 코드다. 이 코드에는 문제점이 있다. 

 

내가 작성한 자바 코드

import java.util.Scanner;



public class 일이될때까지 {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
       int N = scanner.nextInt();  // 2 <= N <= 100,000
       int K = scanner.nextInt();;  // 2 <= K <= 100,000

        int count = 0; // 연산을 한 횟수

        // N이 1이 되면 연산 종료
        while (N != 1){
            // N이 K로 나누어 떨어질 경우 나누고,
            if(N%K == 0){
                N = N/K;
            }else{ // 아닐 경우 1을 뺴기
                N -= 1;
            }
            count++;
        }

        System.out.println(count);
    }
}

 

문제점

 

위 코드는 첫 번째 연산을 할 때 반복문 한 번에 1을 한 번 빼는 방식으로 동작한다. 이런 경우 N이 100억 이상의 큰 수가 되는 경우 프로그램이 너무 느려져 문제가 생길 수 있다.

 

이것을 N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식으로 소스 코드를 작성할 수 있다.

 

수정한 소스 코드

import java.util.Scanner;



public class 일이될때까지2 {

   static public void main(String[] args){
      
       Scanner scanner = new Scanner(System.in);
       int N = scanner.nextInt();  // 2 <= N <= 100,000
       int K = scanner.nextInt();;  // 2 <= K <= 100,000

       int count = 0; //실행 횟수

       while(N!=1){    // N이 1이 될 떄까지 반
           // N이 K로 나누어 떨어질 경우 두 번째 연산 수행, 아닐 경우 첫 번째 연산 수행
           
           if(N % K == 0){
               N = N/K;
               count ++;
               continue; // 두 번째 연산 종료 후 반복문의 처음으로 돌아가기
           }

           // N이 나누어 떨어질 때까지 1씩 빼기
           int target = (N/K) * K;
           count +=  (N - target);
           N = N - target;
       }

       System.out.println(count);
   }
}

 

저자 풀이

github.com/ndb796/python-for-coding-test/blob/master/3/6.java