[백준-10162번 자바/java] 전자레인지 _디버깅의 눈물
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