그리디
-
[Java] 백준 1931 회의실 배정Programming/Algorithm 2021. 3. 24. 01:47
문제 회의의 시작시간, 종료시간이 주어질 때 사용할 수 있는 회의의 최대개수를 출력하는 문제. 풀이 - 처음엔 문제를 잘못 이해했다. - 시작시간이 2 종료시간이 2라고 할 때 시작과 동시에 끝나므로 해당 경우도 갯수에 더해줘야 한다. - 또한 (1 2) (2 2) 인 경우나 (2 2) (2 5) 인 경우 2 회의 모두 결과값에 포함될 수 있다. - 첫번째로 푼 풀이는 다이나믹 프로그래밍이었다. - 현재 인덱스에 대해서 이전의 인덱스를 모두 확인하여 최댓값을 구하게끔 했다. - 이 경우 O(n^2)이라는 시간 복잡도가 나와 N이 10만인 경우 100억의 연산이 필요하다는 문제가 있었다. 당연히 시간초과가 났다. - 두번째로 푼 풀이는 그리디였다. - 사실 회의를 최대한으로 하는 횟수는 매우 간단하게 구할..
-
[Java] 백준 11399 ATMProgramming/Algorithm 2021. 3. 19. 11:09
문제 사람의 수와 각 사람이 돈을 인출하는 데 걸리는 시간이 주어진다. 이 때 모든 사람이 돈을 인출하기 위해 대기하는 총 시간의 최솟값을 출력하는 문제이다. 풀이 인출시간이 빠른 사람이 앞에 오도록해서 사람들의 대기시간을 최소로 만든 뒤에 대기시간의 합을 구하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class b11399 { public static void main(String[] args) throws IOException { BufferedR..
-
[Java] 백준 10610 30Programming/Algorithm 2021. 3. 15. 23:58
문제 숫자 N이 주어진다. 해당 숫자를 이루고 있는 수들을 이용해서 만들 수 있는 가장 큰 30의 배수를 출력하는 문제이다. 풀이 처음에는 받아온 N이라는 숫자를 char[]로 쪼개어서, 만들 수 있는 모든 조합을 만들다가 가장 큰 30의 배수가 나오면 출력하게끔 짰다. 근데 NumberFormat Exception이 발생했다. 다시 문제를 자세히 살펴보니, 주어진 N이라는 수의 자릿수가 최대 10^5라는 조건이 있었다. 최댓값이 10^5(100_000)라는 것으로 착각했던것.. 이 조건을 생각하면 long타입으로도 조합을 만들 수가 없다. 다른 분들의 코드를 참고해서 풀었다. 풀이의 핵심은 다음과 같다. - 30의 배수는 10의 배수이므로 끝자리가 0이다. => N에 0이 포함되어 있지 않다면 30의 ..
-
[Java] 백준 2875 대회 or 인턴Programming/Algorithm 2021. 3. 10. 20:48
문제 대회에 나갈 수 있는 1 팀은 여자2 남자1로 구성되어 있다. 여자는 총 m명 남자는 총 n명이 있다고 할 때 m+n명중 k명은 반드시 인턴에 참여해야한다. 인턴에 참여한 인원은 대회에 참가할 수 없다고 할 때, 만들 수 있는 최대 팀수를 구하는 문제이다. 풀이 - 먼저 만들 수 있는 팀 수의 최댓값(teams)을 구한다. - 만들 수 있는 팀의 개수는 '총 여자 수/2(1팀에 최소로 들어가야하는 여자 수)'와 총 남자 수/1(1팀에 최소로 들어가야 하는 남자 수)' 중 더 작은 값이다. - int teams = Math.min(M/2, N/1) - 총 인원에서 팀에 속한 사람들 (teams * 3)을 뺀 나머지 인원을 구한다. - 이 인원이 K보다 크거나 같아야 K명 이상이 인턴에 참여가능한 것이..
-
[Java] 백준 11047 동전 0Programming/Algorithm 2021. 3. 10. 20:42
문제 n 종류의 동전이 주어진다. 동전을 적절히 사용해서 가치의 합을 K로 만드는 문제이다. 풀이 K보다 작은 동전의 가치중 가장 큰 값으로 K를 나눠 동전의 개수를 구하고 나머지로 K를 초기화한다. K가 0이 되면 사용한 동전의 총 개수를 출력한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inpu..