백준 1590 자바 - 캠프가는 영식 (BOJ 1590 JAVA)

문제 : boj1590

 

  n개의 경우 각각에 대해 만족하는 가장 작은 시각을 찾아보면 된다. n개의 경우 각각에 대해 a가 0부터 C-1까지의 자연수라고 할 때, 다음 식을 통해 나온 값 중 최초로 T 이상의 값이 나오는 경우가 해당 경우의 최소수치이다.

  n개에 대해 각각 위의 최소수치를 구하고, 그 중 가장 작은 값이 답이다. 이 때 C는 최대 100 이므로 0부터 99까지 전부 다 해봐도 최대 O(NC) 정도의 시간복잡도이므로 전부 다 해보면 된다. 따라서 브루트 포스이며, 최초로 T 이상의 값이 나올 경우 바로 중지하면 되고 추가로 f(a)가 이미 이전에 나온 값보다 큰 경우엔 더이상 볼 필요도 없으므로 백트래킹도 가미하면 좀 더 효율적으로 할 수 있다.

 

  코드에서 while문 내의 's < t'부분이 최초 한번 t를 넘어가면 중지하는 부분이고, '--c>0'은 0부터 c-1 까지 확인하는 부분, 's < answer'은 이전에 나왔던 값보다 큰 경우 더이상 보지 않고 넘어가기 위한 부분이다. 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
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 n = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        int answer = Integer.MAX_VALUE;
        while (n-->0) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int i = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            while (s < t && --c>0 && s < answer) s+=i;
            if (s >= t) answer = Math.min(s, answer);
        }
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer-t);
    }

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