Greedy-1이 될 때까지

문제

• 책, ‘이것이 취업을 위한 코딩 테스트다’ / ch3 Greedy / 예제 3-4 (p.99)

어떤 수를 N이 1이 될 때까지 다음 두가지 과정 중 하나를 반복적으로 수행.

1. N에서 1을 뺀다
2. N을 K로 나눈다 (단 N이 K로 나누어 떨어져야한다)

최소 연산 횟수를 구하시오.

Step 1. 문제 접근

나누는것이 가장 빠르게 수를 줄일 수 있는 방법이므로, 나누는것이 가능하다면 무조건 나누고 불가능하다면 뺄셈을 한다.

즉 최선책과 차선책이 존재하고 최선책을 가능한 한도에서 최대한 많이 반복하는 것이 최적해를 구하는 것

Step 2. 선택한 알고리즘

Greedy 알고리즘

• Greedy (탐욕법)

  현재 상황(고려하는 turn)에서 당장 좋은 것만 고르는 방법 (이후는 고려하지 X )

Step 3. 선택 이유

매 연산을 선택할 때마다 다음 연산을 고려하지 않고 나눌 수 있으면 무조건 나누는 방식, 즉 각 연산에서 최적해를 구하는것이 궁극적으로 총 연산횟수를 줄이는 최적해가 도출되므로 Greedy를 선택한다.

이 때 시간복잡도는 최악의 경우 계속 뺄셈만을 반복하는 O(N)이 된다.

Step 4. 구현 (코드)

package greedy;

import java.util.Scanner;

public class 숫자카드게임 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 
		
		// 숫자카드 행, 열 입력  
		int n = sc.nextInt() ; 
		int m = sc.nextInt() ;
		int result = 0 ; 
		
		for(int i = 0 ; i < n ; i++) {
			int min_value = 10001 ; 
			for(int j = 0 ; j < m ; j++) {
				/*
				 * 아이디어 주목 : 숫자카드를 한번에 완성시킨 후 비교하는게 아닌 입려 받으면서 최솟값 갱신   
				 	=> 각 줄의 최솟값 도출 
				 */
				int x = sc.nextInt(); 
				min_value = Math.min(min_value, x); 
			} // j 
			// 행의 최솟값을 도출한 후 바로 기존 최댓값과 비교하여 갱신 
			result = Math.max(result, min_value) ; 
		} // i 
		System.out.println(result) ; 
	} // main 
} // class