[자바] 백준 10162 - 전자레인지 (java)

 문제 : boj10162

---

 

필요 알고리즘 개념

•  그리디 알고리즘
  • 규칙을 정해, 매번 해당 규칙을 적용시켜 답을 구하는 그리디 알고리즘 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  최소 버튼 조작 횟수이므로, 그냥 초가 큰 버튼부터 눌러주면 된다. A,B,C를 초로 변경해주면 300,60,10 이므로 300을 누를 수 있는만큼 누르고, 60을 누를 수 있는 만큼 누르고, 10을 누를 수 있는 만큼 누르면 된다. 근데 주의할 점은 이게 매번 통하는 방식이 아니다. 단순히 큰 것 부터 누른다고 매번 가능한게 아니고, 서로 배수 관계이기 때문에 이게 가능한거다.

 

  예를들어 17, 11, 2 이렇게가 A,B,C 였다고 해보자. 이것도 마찬가지로 큰 것 부터 빼주면 될까? 안된다. T가 22일 경우, 큰 것 부터 빼주면 22-17 = 5가 되어 -1을 출력해줘야 하지만 실제론 11을 2번 눌러주면 된다. 아무튼 그러니 티어가 낮은 문제에서 이렇게 했다고 매번 이게 가능한게 아니다. 주어진 값들이 배수관계일 때만 성립한다. 그게 아니라면 이제 DP(동적 계획법)을 써야하고, 그 대표적인게 유명한 냅색(Knapsack)류의 문제이다.

 

  아무튼 이 문제는 그냥 큰것부터 선택해주는 그리디 알고리즘 개념을 적용시키면 된다.

예를들어 T=100인 경우, 300으론 못나누니 넘어가고 -> 60은 한번 누를 수 있고 T=40이 된다. -> 10을 4번 누를 수 있다.

위의 과정은 나누기와 나머지 연산을 통해 가능하다. 코드를 참고해보자.

cnt[i] += t/TIME[i];
t%=TIME[i];

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static final int[] TIME = {300, 60, 10};
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int[] cnt = new int[3];
        for (int i = 0; i < 3; i++) {
            if (t < TIME[i]) continue;
            cnt[i] += t/TIME[i];
            t%=TIME[i];
        }
        System.out.println(t!=0?-1:String.format("%d %d %d", cnt[0], cnt[1], cnt[2]));
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}