[그리디] 1이 될 때까지

문제 설명

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

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

N이 1이 될 때까지 수행해야 하는 최소 횟수를 구하는 프로그램 작성하기

 

1. 사용 알고리즘 

그리디

 

2. 문제 해결 아이디어

수행 횟수가 최소가 되기 위해서는 N을 K로 최대한 많이 나누면 된다. N에서 1을 빼는 것보다 숫자가 더 빠르게 줄어들기 때문이다. 

 

3. 코드

구현 방식1)

if-else를 통해 조건에 따라 다르게 수행되도록 하기 

import java.util.Scanner;

public class q3 {

	public static void main(String[] args) {
		//while문 돌리고 -> K로 나눠떨어질때는 무조건 나누고 & 아니면 N-1하고 
		Scanner kbd = new Scanner(System.in);
		
		int N, K;
		N = kbd.nextInt();
		K = kbd.nextInt();
		
		int count = 0; //수행 횟수 
		while(true) {
			if(N == 1) break; //N이 1이 되면 멈춤 
			else {
				if(N%K == 0) N /= K; //N이 K로 나누어 떨어질 때 
				else N -= 1;
				count++;
			}
		}
		
		System.out.println(count);
	}
}

구현 방식2)

N%K == 0이 될 때까지 한번에 N에서 1을 빼기 

import java.util.Scanner;

public class q3_2 {

	public static void main(String[] args) {
		//while문 돌리고 -> K로 나눠떨어질때는 무조건 나누고 & 아니면 N-1하고 
				Scanner kbd = new Scanner(System.in);
				
				int N, K;
				N = kbd.nextInt();
				K = kbd.nextInt();
				
				int count = 0, target; //수행 횟수
				while(true) {
					//N%K == 0이 될 때까지 1씩 한번에 빼기 
					target = (N/K)*K; 
					count += (N-target);
					N = target;
                    
					//반복 끝낼 조건 : N이 K보다 작을 때(더 이상 나눌 수 없을 때)
					if(N < K) break;
					
                    //K로 나누기
					count++;
					N /= K;
				}
				
				count += (N-1);
				System.out.println(count);
	}
}