[Java] [이코테] 1이 될 때까지

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 ≤ 100,000)과 K(2≤ K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

[출력 조건]

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

 

처음에는 그냥 1차원적으로 생각한게,

1. 그리디 알고리즘 적용

2. N 이 K의 배수가 될때까지 -1 반복 (연산횟수 1씩 증가)

3. N을 K 로 나누기

를 적용하여 코드를 작성하였다 .  그 결과는 아래와 같다

<내가 작성한 코드>

package greedy;

import java.util.Scanner;

public class Until1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        int answer = 0;

        // n을 k의 배수로 만들자 그리고 n을 k로 나누기

        // 만약 n이 k의 배수가 아니라면, n-1을 한다
        while(n > 1) {
            if (n % k ==0) {
                n /= k;
            }
            else{
                n -= 1;
            }
            answer++; //연산횟수 1 증가
        }
        System.out.println(answer);
    }
}

 

코드는 정상적으로 작동하지만, 예를 들어 N이 100000 이라고 가정하고, k가 2라고 가정했을 때, 위 코드는 1씩 빼면서 나누기를 하는 연산을 계속 하게 되어 연산 횟수가 많아 복잡도가 O(N) 까지도 수렴할 수 있다고 생각했다.

 

아래는 교재의 해답 코드를 보고 작성한 코드이다

<개선된 코드>

package greedy;

import java.util.*;

public class Until1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        int calCount = 0 ;

        //-1을 최대한 적게 해줘야 한다

        while (true) {
            int target = (n / k) * k;
            calCount += (n - target);
            n = target;

            if (n < k) { // n이 k보다 작으면 나누기 불가
                break;
            }

            calCount++;
            n /= k;
        }
        System.out.println(calCount);
    }
}

 

• target = (n / k) * k;는 n이 k로 나누어떨어지는 값으로 만들어서, 그 사이에 1을 몇 번 뺐는지를 한 번에 계산한다.
• calCount += (n - target);는 그 사이에 몇 번 -1 연산을 했는지 누적한다.

• if (n < k)는 n이 k보다 작아져서 더 이상 나눌 수 없을 때 루프를 빠져나감.
• 그 외에는 n /= k로 나눔을 수행하고 calCount++로 나눗셈 연산을 카운트.

 

즉, 이 해답의 핵심은 한 번에 n을 k로 나누어떨어지는 수로 만들기 위해 target을 계산하고, n - target만큼 한 번에 처리하여 반복을 최소화하는데 있다.

처음에는 아무 생각 없이 코드 짜다가.. 입력 값이 클 때를 고려하지 못하고 짰는데, 이전 게시물에서도 포스팅 했다시피 언제나 문제와 입력 값을 잘 읽고 고려해야한다..

다음 문제 부터는 조금 더 생각하고 작성 하도록 하자

그럼 20000!