[Java] 백준 7481번 - ATM놀이 (실버 1)
혼자 힘으로 풀었는가? X
알고리즘 분류
- 수학
- 정수론
- 비둘기집 원리
https://www.acmicpc.net/problem/7481
문제
ATM에는 다른 종류 두 가지의 지폐가 굉장히 많이 있다. ATM에서 돈을 찾을 때 ATM은 예금주의 잔액을 넘지 않는 범위에서 정확한 양의 돈을 지급한다. 꿍은 지폐를 많이 들고다니고 싶지 않기때문에 되도록이면 가장 적은 수의 지폐를 들고다니고 싶어한다.
여러분은 가장 적은 수의 지폐로 꿍이 인출하려는 금액을 정확히 지급해주는 ATM을 만들어야 한다. ATM을 만들 때, ATM안에는 무제한으로 지폐가 들어있다고 가정해도 좋다.
입력
첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있으며 각 줄에는 a, b(ATM에 있는 지폐의 종류)와 S(꿍이 인출하려는 금액) 세개의 정수로 이루어져 있으며 공백으로 구분되어 있다.
출력
각 테스트케이스에 대해 ATM에서 인출되는 두 가지 지폐의 장수를 각각 출력한다. 만약 가능한 경우가 없다면 "Impossible" (따옴표 제외)이라고 출력한다.
제한
- 1 ≤ T ≤ 100
- 1 ≤ a, b ≤ 10000
- a ≠ b
- 0 ≤ S ≤ $10^9$
문제 자체는 단순하다. 주어진 두 수로 두 번 나눠서 나머지가 0일때 출력하는거다. 조건은 두 수중에 더 큰 수로 나누었을때가 정답이다.
하지만 단순하게 풀면 시간초과가 발생한다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuffer sb = new StringBuffer();
int T = Integer.parseInt(st.nextToken());
for(int t=0; t<T; t++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
int max = a>b ? a:b;
int min = a<b ? a:b;
int limit = s / max;
boolean [] flag = new boolean[min];
boolean check = false;
for(int i=limit; i>=0; i--) {
int remain = s - max*i;
int mod = remain % min;
if(flag[mod]) {
break;
}
flag[mod] = true;
if(mod == 0) {
check = true;
if(max == a) {
sb.append(i+" "+remain/min+"\n");
} else {
sb.append(remain/min+" "+i+"\n");
}
break;
}
}
if(!check) sb.append("Impossible\n");
}
System.out.println(sb);
}
}
flag 배열을 만들어서 나머지를 한번 더 확인할 필요 없도록 하였다.
나는 의문이 들었다.
if(mod == 0) 으로 어차피 확인하지 않나? 싶었는데 내가 생각지도못한 부분이 있었다.
flag로 나머지를 확인하는 이유는 동일한 나머지가 나온다면, 해당 수는 영원히 나누어 떨어지지 않기 때문에 그대로 종료하는 것이다.
만약 flag가 없이 계속해서 비교한다고 생각해보자.
2 4 111이 주어졋다.
큰 수인 4를 기준으로 111을 나누면 27부터 시작한다.
111 - (4*27) = 3
3 % 2 =1 이다.
그다음 26으로 줄여서
111 - 4*26 = 7
7 % 2 = 1이다.
우리는 이로써 알 수 있다.
27이 0이 될 때 까지 나누어도 결국 2로 나누면 나머지는 1이고 절대 나눠지지 않는다는 것을
만약 flag가 없다면 이 행동을 27번 반복해야 한다.
하지만 flag고 확인한다면 2번만 반복하고 반복문을 종료 후 Impossible을 출력하고 끝내면 된다.
이로써 시간초과를 피할 수 있게 된다.