[자바] 백준 1214 - 쿨한 물건 구매 (java)

 문제 : boj1214

---

 

필요 알고리즘 개념

• 수학, 정수론, 브루트포스
  • 브루트포스로 풀 수 있긴한데, 수학적으로 시간복잡도를 줄여야한다.

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

 

---

 

풀이

  이 문제를 풀기전에, 혹시 개념이 잘 떠오르지 않는다면 '백준 14916번 : 거스름돈' 을 먼저 풀어보자. dp로도 풀 수도 있겠지만, 브루트포스로 푸는 경우를 생각해보자. 내 경우엔 이와 비슷한 문제를 풀었던 기억이 나서 거기서 시간을 깎아내서 맞출 수 있었다.

  위는 거스름돈 문제의 내용이다. 위 문제를 브루트포스로 어떻게  풀까? 최소개수이므로 당연히 5원을 최대한 많이 써야 하고, 정확히 n원이 되야할 것이므로 다음과 같은 로직으로 진행할 것이다.

'n이내에서 최대로 사용할 수 있는 5원의 개수 x개에서 x를 1씩 줄여가면서, 5원이 0개가 될때까지 n-5*x가 2로 나누어 떨어지는지 확인한다.'.

 

  예를들어 n이 18인 경우 n/5 = 3이므로 최대 5원의 수는 3개까지 쓸 수 있다. 5원을 3개->0개로 낮춰가면서 진행해보자.

1. 5원을 3개 = 15원이고 남는건 3원이므로 2원으로 만들 수 없다.

2. 5원을 2개 = 10원이고 남는건 8원이므로 2원 4개를 추가해 만들 수 있다. -> 따라서 이게 답이다.

 

---

  이 문제도 마찬가지로 접근했다. p와 q중 큰 수를 a, 작은 수를 b라고 둔다. 이 때, 처음에 만약 b가 1이거나, b가 2면서 d가 짝수인 경우, d가 애초에 a나 b로 나누어 떨어지는 경우라면 그대로 d를 출력해주면 된다.

 

  a를 기준으로 총 몇번 진행해야하는지 기준을 잡는다(위에서 5원으로 기준 잡았던 것 처럼). 다만 이 문제에서는 정확히 d가 아니라 d 이상인 값 중 차이가 가장 작은걸 구해야하므로, d/a+1이 기준점이다. 그리고 a를 사용하는 갯수를 의미하는 i를 d/a+1부터 0까지 감소시키거나 0부터 증가시키면서(어차피 이번엔 갯수의 최소값을 구하는게 아니라, 차이의 최소값을 구하는 것이므로 상관 없음) 진행한다. 이 때 d에서 남은 수치는 d-a*i가 될 것이고, 이제 그 남은 값을 가지고 b로 만들 수 있는 d 이상의 최소 차이값을 구하면 된다.

 

  대략 여기까지하면 a가 최소 3정도 될테니, 대략 O(3억)정도로 볼 수 있다. 어떻게든 될꺼라 생각했는데 여기까진 일단 시간초과가 났다. 그래서 좀 더 생각한 방식이, 어차피 a를 가지고 처리 후 남은 값(코드의 remain)을 가지고, b를 이용해 최소한의 차이를 만든다(int tmp = b-remain%b;). 그렇다면 그 최소값은 b이하임이 보장된다. 그리고 증명은 명확히 하지 못하겠지만, 돌려보며 디버깅을 해보니 tmp가 다시 나올 경우 사이클이 생기는걸 발견했다. 그렇다면 사이클이 생기는 경우엔 거기서 멈춰도 될 것임을 알 수 있다. 따라서 HashSet을 사용해 이미 나온 tmp값을 저장해두어서 사이클이 생기는걸 막았다.

 

  위와 같이 해볼 경우, 대략 d/a 번에 걸쳐 루프가 진행된다. 그리고 사이클이 생기기 전까지 b번 이하의 tmp 값이 생성된다. 그럼 최대 min(d/a, b)번 수행될 것임을 알 수 있고, a>=b이다. 그렇다면 최악의 경우, 즉 min(d/a, b)가 가장 커지는 경우는 a==b이면서 min(d/a, b)가 최대가 되는 경우인 a == b == sqrt(d) 인 경우이다.

따라서 O(sqrt(d)) 으로 이 문제를 풀 수 있게된다. 수학이 약해 명확히 증명은 못하겠지만, 이전에 풀었던 개념으로 시작해서 -> 시간을 깎기 위해 규칙성을 발견했고 -> 그 규칙성이라면 시간 복잡도를 줄일 수 있음을 보였다.

 

 

 

---

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int d = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        int a = p>q?p:q;
        int b = p>q?q:p;
        if (b == 1 || b == 2 && d%2==0 || d%a==0 || d%b==0) {System.out.println(d); return;}

        int limit = d/a+1;
        int answer = a-1;
        HashSet<Integer> hs = new HashSet<>();
        for (int i = 0; i <= limit; i++) {
            int remain = d-a*i;
            if (remain>0 && remain%b == 0) {
                System.out.println(d);
                return;
            }
            if (remain < 0) remain+=b;
            int tmp = b-remain%b;

            if (hs.contains(tmp)) break;
            hs.add(tmp);
            if (answer > tmp)
                answer = tmp;
        }
        System.out.println(d+answer);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}