코딩테스트

[백준-10162번 자바/java] 전자레인지 _디버깅의 눈물

디버깅의 눈물 2022. 10. 25. 15:56

https://www.acmicpc.net/problem/10162

 

10162번: 전자레인지

3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은

www.acmicpc.net

 

 

 

 

전자레인지 성공서브태스크

 
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 64 MB 25574 15118 13049 59.927%

문제

3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 각각 5분, 1분, 10초이다.

냉동음식마다 전자레인지로 요리해야할 시간 T가 초단위로 표시되어 있다. 우리는 A, B, C 3개의 버튼을 적절히 눌러서 그 시간의 합이 정확히 T초가 되도록 해야 한다. 단 버튼 A, B, C를 누른 횟수의 합은 항상 최소가 되어야 한다. 이것을 최소버튼 조작이라고 한다. 

만일 요리시간이 100초라고 하면(T=100) B를 1번, C는 4번 누르면 된다. 이와 다르게 C를 10번 눌러도 100초가 되지만 이 경우 10번은 최소 횟수가 아니기 때문이 답이 될 수 없다. 이 경우 B 1번, C 4번, 총 5번이 최소버튼 조작이다. 그리고 T=234와 같이 3개의 버튼으로 시간을 정확히 맞출 수 없는 경우도 있다. 

여러분은 주어진 요리시간 T초를 맞추기 위한 최소버튼 조작 방법을 구하는 프로그램을 작성해야 한다. 

입력

첫 번째 줄에는 요리시간 T(초)가 정수로 주어져 있으며 그 범위는 1 ≤ T ≤ 10,000 이다. 

출력

여러분은 T초를 위한 최소버튼 조작의 A B C 횟수를 첫 줄에 차례대로 출력해야 한다. 각각의 횟수 사이에는 빈 칸을 둔다. 해당 버튼을 누르지 않는 경우에는 숫자 0을 출력해야한다. 만일 제시된 3개의 버튼으로 T초를 맞출 수 없으면 음수 -1을 첫 줄에 출력해야 한다. 

서브태스크

번호배점제한
1 30 T ≤ 60
2 30 T ≤ 300
3 40 T ≤ 10,000

예제 입력 1 복사

100

예제 출력 1 복사

0 1 4

예제 입력 2 복사

189

예제 출력 2 복사

-1

 

 

 


 

 

 

체크 포인트

 

1. 그리디 알고리즘(Greedy Algorithm) 이용

 

-현재의 가장 최적의 답을 선택해 적합한 결과를 도출해내는 '그리디 알고리즘'을 이용하는 문제이다.

-그리디 알고리즘의 대표적 문제 유형으로는 활동 선택 문제나 거스름돈 문제 등이 있다.

 

 

https://tears-of-debugging.tistory.com/60

 

[백준-5585번 자바/java] 거스름돈 _디버깅의 눈물

https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게..

tears-of-debugging.tistory.com

 

 

 

-이 문제도 거스름돈 문제와 같은 맥락의 문제라고 볼 수 있다. 전자레인지 버튼 시간 5분, 1분, 10초를 동전의 종류라고 생각하고, 전자레인지 작동 시간 T를 거스름돈이라고 생각하면 된다.

-그리디 알고리즘이므로 현재 사용 가능한 큰 수의 버튼을 사용해 최소의 총 버튼 사용수를 찾아야한다.

 

 

 

 

2. 버튼의 종류를 time[]배열에 입력

 

 

		static int[] time;

		// 전자레인지 작동 버튼의 종류를 담는 배열
                time = new int[3];
		time[0] = 300;
		time[1] = 60;
		time[2] = 10;

 

-버튼의 종류 5분(300), 1분(60), 10초를 time[] 배열에 담아주었다. 

 

 

 

 

 

3. 단위가 가장 큰 버튼부터 사용시간 처리(그리디 알고리즘)

 

 

		// 단위가 큰 버튼부터 탐색 시작
		for(int i=0; i<3; i++){
			// 해당 버튼의 시간보다 작동시간이 크거나 같다면,
			if(time[i]<=T){
				// 몫을 정답에 입력
				answer += (T/time[i]) + " ";
				// 작동시간 감소 처리
				T = T%time[i];
			}
			// 해당 버튼의 시간보다 작동시간이 작다면,
			else{
				// 버튼 이용 불가 처리
				answer += "0 ";
			}
		}

 

 

-현재 사용할 수 있는 가장 큰 단위의 버튼(최적)을 이용해 전자레인지 사용시간을 구성하는 '그리디 알고리즘'을 활용한다.

-해당 버튼을 더이상 사용할 수 없는 경우, 다음으로 사용할 수 있는 가장 큰 버튼을 이용해 동일한 로직을 반복하며 최적해를 구해나간다.

 

 

 

-예시1)의 경우 전자레인지 총 사용 시간은 100초이고, 이를 바탕으로 최소의 버튼 수를 구하는 과정을 추론하자면,

 

1)가장 큰 단위의 버튼 300초는 총 사용 시간 100초보다 크기 때문에 0을 입력한다.

 

2)다음으로 가장 큰 단위의 버튼 60초는 총 사용 시간 100초보다 작기 때문에, 100을 60으로 나눈 몫 1을 입력하고, 나머지인 40은 새로운 총 사용 시간이 된다.

 

3)다음으로 가장 큰 단위의 버튼 10초는 총 사용 시간 40초보다 작기 때문에, 40을 10으로 나눈 몫 4를 입력하고, 나머지인 0은 새로운 총 사용 시간이 된다.

 

4)총 사용 시간이 0이므로, 현재까지 입력받은 값 0 1 4를 출력한다.

 

 

 

 

 

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


class Main{
	
	static int[] time;
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// 전자레인지 총 작동 시간
		int T = Integer.parseInt(st.nextToken());
		
		// 전자레인지 작동 버튼의 종류를 담는 배열
		time = new int[3];
		time[0] = 300;
		time[1] = 60;
		time[2] = 10;
		
		
		solution(T);
		
	}// end of main
	
	
	
	static void solution(int T) {

		String answer = "";

		// 단위가 큰 버튼부터 탐색 시작
		for(int i=0; i<3; i++){
			// 해당 버튼의 시간보다 작동시간이 크거나 같다면,
			if(time[i]<=T){
				// 몫을 정답에 입력
				answer += (T/time[i]) + " ";
				// 작동시간 감소 처리
				T = T%time[i];
			}
			// 해당 버튼의 시간보다 작동시간이 작다면,
			else{
				// 버튼 이용 불가 처리
				answer += "0 ";
			}
		}
		
		// 총 사용 시간을 0으로 만들 수 없다면,
		if(T!=0){
			answer = "-1";
		}
		
		System.out.println(answer);
	}
	
	
	
} // end of Main