[자바] 백준 7481 - ATM놀이 (java)

 문제 : boj7481

---

 

필요 알고리즘 개념

• 정수론, 수학
  
  • 나머지 연산을 사용해 풀 수 있다.
• 비둘기집의 원리
  • 현재는 테스트케이스가 너무 빈약해서 의미 없지만, 테스트케이스 추가 시 통과하려면 비둘기집의 원리로 풀 수 있다.

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

 

---

 

풀이

  a와 b 중 큰 수를 hi, 작은 수를 lo 라고 해보자.

우선 가장 적은 수의 지폐를 만들려면, 가능한 경우의 수 중 hi가 가장 큰 경우를 찾아야 한다.

따라서 hi지폐를 S/hi (소수점 내림) 장 가지고있는 것에서 시작해서, 1장씩 빼주면서 lo로 나누어떨어지는지 보면 된다.

 

  예를들어 "2 3 7" 이라는 입력이라면 hi는 3, lo는 2이다.

S/hi는 2이다. 따라서 hi를 2장 가지는 경우부터 생각해보자.

1. hi * 2 = 6이고, 그럼 S-hi*2 = 1이다. 1은 lo로 나누어떨어지지 않으므로 패스한다.

2. hi * 1 = 3이고, S-hi*1 = 4다. 4는 lo로 나누어떨어지므로 이 경우가 가장 적은 수의 지폐로 정확한 양의 돈을 지급한 경우이다.

 

  위처럼 하면 답은 구할 수 있을 것 같다. 다만 문제는 S의 최대치가 10^9 이라는 점이다.

예를들어 "2 4 999999999"인 경우를 생각해보자.

999999999/4 = 2억5천정도다. 2억 5천정도부터 1씩 감소시키면서 2로 나누어떨어지는지 봐야하는데, 이 경우 사실 답은 Impossible이다. 즉 위의 로직으로만 하면 O(2억5천)이 되니 당연히 시간초과다. 심지어 테스트케이스가 몇십개가 있고 그게 전부 위의 경우라면 뭐 당연하게도 시간초과다.

 

  따라서 어떻게 시간초과를 피할지 생각해봐야하는데, 사실 이 문제 테스트케이스가 너무 빈약해서 위와 같은 테스트케이스가 없다;; 그래서 이런 경우 생각 안하고 무지성으로 브루트포스 돌려도 통과된다. 이 부분은 당연히 다른분이 테스트케이스 추가 요청을 넣어서 언젠가 추가될것 같다. 현재는 그래서 실버티어로 잡혀있는데, 사실 테스트케이스 추가되면 골드급으로 올라갈 문제이다.

 

  아무튼 시간초과를 피하는건 비둘기집의 원리로 가능하다.

매번 S-hi*x 라는 수치가 lo로 나누어떨어지는지 봐야하고, lo로 나눈 나머지는 항상 lo 미만이다.

그리고 매번 *x에서 x가 감소함에 따라 hi만큼 더해진 수치에 lo로 나누어 떨어지는지 확인하고 있다.

따라서 이미 이전에 나온 나머지값이 다시한번 나온다면 그 이후로는 이전까지의 나머지가 반복해서 나오고, 나누어떨어질 일이 절대 없음을 알 수 있다. 그러므로 최대 lo 번만 확인하면 된다 (비둘기집의 원리).

따라서 이렇게 짜면 최종적으로 시간복잡도는 O(2억5천 * 테스트케이스 수)이라는 어마무시한 시간복잡도에서 O(min(S/hi, lo))로 줄어들고, a와 b는 최대 10000이므로 O(10000 * 테스트케이스 수)으로 풀 수 있다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

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

    public void solution() throws Exception {
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (tc-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            if (s == 0) {
                sb.append("0 0\n");
                continue;
            }

            if (a > s && b > s) {
                sb.append("Impossible\n");
                continue;
            }

            int hi = a>b?a:b;
            int lo = a>b?b:a;
            int limit = s/hi;
            boolean chk = false;
            boolean[] v = new boolean[lo];
            for (int i = limit; !chk && i >= 0; i--) {
                int remain = s - hi * i;
                int mod = remain%lo;
                if (v[mod]) {
                    chk = false;
                    break;
                }
                v[mod] = true;
                if (mod != 0) continue;

                chk = true;
                if (hi == a) {
                    sb.append(i + " " + (remain/lo)).append('\n');
                } else {
                    sb.append((remain/lo) + " " + i).append('\n');
                }
            }
            if (!chk)
                sb.append("Impossible\n");
        }
        System.out.print(sb);
    }

    private int getMin(String hhmm) {
        String[] split = hhmm.split(":");
        return Integer.parseInt(split[0]) * 60 + Integer.parseInt(split[1]);
    }
}