그리디 알고리즘23 [백준]2262: 토너먼트 만들기 - JAVA https://www.acmicpc.net/problem/2262 풀이n명의 선수들의 랭킹이 주어진다. 2명씩 대결을 붙여 우승자를 가리는 토너먼트를 만들어야 한다. 1. 랭킹이 가장 낮은 선수를 찾는다.2. 해당 선수의 좌, 우를 살펴 차이가 적게나는 사람과 대결을 한다.3. 선수가 1명 남을때까지 반복한다. 위의 과정으로 풀 수 있었다. 예제에는 `1 6 2 5 3 4` 로 주어졌다. 첫 번째로 6을 골라 양 옆에 있는 1과 2 중 2를 선택하여 대결한다. `1 2 5 3 4`가 되고, 같은 방식으로 5를 골라 3과 대결한다. 1 6 2 5 3 4 -> 6 vs 2 (4)1 2 5 3 4 -> 5 vs 3 (2)1 2 3 4 -> 4 vs 3 (1)1 2 3 -> 3 vs 2 (1)1 2 -> 2 v.. 2024. 9. 9. [백준] 30960: 조별 과제 - JAVA https://www.acmicpc.net/problem/30960 풀이N명의 학생들의 조를 편성해야한다. 1개의 조만 3명으로 편성되고 다른 조들은 2명으로 편성된다. 학생에게 숫자가 부여되는데 각 조 안에서 (최댓값 - 최솟값)이 해당 조의 어색함이 된다. 어색함의 합의 최소가 되도록해야한다. 먼저 입력받은 배열을 정렬했다. 정렬 후 2개의 배열을 만들어서 하나는 앞에서부터 시작, 하나는 뒤에서부터 시작하여 누적합을 담았다. 누적합은 어색함들의 합을 더해줬다. `left[i] += (arr[i] - arr[i-2])` 이런식으로 어색함을 더해줬고, i는 2찍 증가시키면서 진행했다. 누적합 배열 2개를 만든 후, 어느 지점에서 3명인 조를 시작해야 어색함이 최소가될지 구해줬다. 메모리: 84096K.. 2024. 6. 25. [백준] 23889: 돌 굴러가유 - JAVA https://www.acmicpc.net/problem/23889 풀이마을들이 일자로 배치되어있고 돌은 벽을 만날때까지 왼쪽에서 오른쪽으로 굴러간다. 마을에는 모래성이 있어서 돌이 굴러가면 모래성이 다 부서진다. 벽을 세워 돌을 막을 수 있는데 모래성이 가장 적게 부서지게 세워야 한다. 돌의 위치와 몇개의 모래성을 부수는지 이차원배열에 담았다. 먼저 돌이 굴러가기 시작하는 위치를 배열에 넣고, 돌의 위치를 기준으로 다음 돌까지 모래성의 개수를 합하여 배열에 넣었다. 부수는 모래성의 개수를 기준으로 내림차순 정렬하고, 가장 많은 모래성을 지킬 수 있는 경우가 두 가지 이상 존재할 경우, 사전순으로 가장 빠른 답을 출력해야 하므로 모래성의 개수가 같을 경우 돌의 위치를 기준으로 오름차순 정렬하였다. 벽의 .. 2024. 6. 20. [백준] 14527: Paired Up - JAVA https://www.acmicpc.net/problem/14527 풀이소들의 수와 milk output이 주어진다. milk output을 기준으로 정렬했다. 투포인터를 이용하여 양쪽에서 가운데를 향해 가면서 소의 수를 감소시키고, 0이되면 다음으로 넘어간다. 이때 milk output의 합을 정답에 갱신하면 되는 문제였다. 메모리: 46184KB시간: 3044ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStream.. 2024. 6. 10. [백준] 1263: 시간 관리 - JAVA https://www.acmicpc.net/problem/1263 풀이해야 할 일들 n개가 일을 처리하는데 걸리는 시간(s), 마감시간(t)이 주어진다. 이차원배열에 s와 t를 넣고 정렬하는데, 이때 정렬기준은 마감시간을 내림차순으로 정렬했다. 마감시간이 마지막인 것 부터 걸리는 시간을 빼주면 일을 언제 시작해야 하는지 구할 수 있다. 일을 시작해야할 시간을 갱신하면서 이 시간이 바라보고있는 일의 마감시간보다 작다면 하던대로 빼주고, 크다면 시작해야 할 시간을 현재 마감시간에서 걸리는 시간을 빼준 값으로 갱신한다. 메모리: 14576KB시간: 148ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static v.. 2024. 5. 31. [백준] 23843: 콘센트 - JAVA https://www.acmicpc.net/problem/23843 풀이충전기 m개로 n개의 전자기기를 충전해야한다. 전자기기마다 충전이 완료되는데 필요한 시간이 달라서 충전기에 전자기기를 적절하게 배치해야한다. 충전기가 비어있다면 충전에 걸리는 시간이 가장 긴 기기를 배치하는 게 적절했다. 따라서 우선순위큐를 이용해 시간이 오래걸리는 순으로 뽑아서 충전기에 넣었다. 충전기에 넣으면서 걸리는 시간을 정답에 갱신하면된다. 메모리: 15476KB시간: 180ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Charger { PriorityQueue chargers; Priority.. 2024. 5. 22. [백준] 3109: 빵집 - JAVA https://www.acmicpc.net/problem/3109 풀이첫번째 열에서 마지막 열까지 파이프를 이어야한다. 이때 이동은 `{ -1, 1 }`, `{ 0, 1 }`, `{ 1, 1 }` 으로 할 수 있다. 탐색 방향 순서를 위에서부터 채우기 위해 -1, 0, 1 순으로 탐색한다. 배열에 방문했다는 체크를 하면서 탐색하며, 마지막까지 같다면 개수를 늘리고, `true`를 리턴한다. 실패할 경우 `false`를 리턴하여 종료한다. 방문 체크를 먼저 하고 탐색을 보냈기 때문에 실패한 칸은 다시 가보지 않아도 되게하여 시간초과를 해결할 수 있었다. 메모리: 34748KB시간: 400ms언어: Java 11import java.io.*;import java.util.*;public class Main.. 2024. 5. 19. [백준] 1744: 수 묶기 - JAVA https://www.acmicpc.net/problem/1744 풀이길이 n의 수열이 주어지고, 이 수열의 합을 구하는 문제이다. 수열내의 두 수를 묶어 그 수들을 곱하는 것으로 계산 할 수 있다. `{-1, 2, 1, 3}` 과 같은 수열이 있다면, 2와 3을 묶어 6으로 만들고, `-1 + 1 + 6 = 6` 으로 6이 최대값이 된다. 음수는 같은 음수끼리 곱하거나, 0과 곱할 때 합에서 이득을 볼 수 있으므로 0이하인 것들은 minus 리스트에 담고, 0보다 큰 수들은 plus 리스트에 담았다. 두 리스트를 정렬해서 minus에 있는 것들은 작은 순으로 2개씩 묶고, plus에 있는 수들은 큰 순으로 2개씩 묶었다. 다만, 1의 경우는 `{1, 1}` 의 수열에서 볼 때, `1 + 1` 이 `1 .. 2024. 5. 19. [백준] 2437: 저울 - JAVA https://www.acmicpc.net/problem/2437 풀이저울추들을 이용하여 무게를 측정하는데 측정할 수 없는 최소값을 구하는 문제이다. 방법이 안떠올라서 정답을 찾아봤다... 먼저 추의 무게들을 정렬하여 작은 것부터 꺼낸다. 올리려는 저울추의 무게가 지금까지 올린 무게의 합 + 1 보다 크다면 무게의합+1이 최소값이 된다. 올린 무게의 합을 sum이라고하면 이는 1~sum까지 무게를 측정할 수 있다는 말이다. sum = 5인 상태에서 다음 저울추가 6이라면 sum + 6까지 무게를 잴수있다. 하지만 다음 저울추의 무게가 7이라면 sum + 1인 6이 측정할 수 없는 최소값이 된다. 메모리: 14384KB시간: 136ms언어: Java 11import java.io.*;import java... 2024. 5. 19. [백준] 20207: 달력 - JAVA https://www.acmicpc.net/problem/20207 풀이일정들의 시작, 종료 날짜가 주어지고, 달력에 배치해야 한다. 달력에 배치할 때 주의해야 할 규칙은 다음과 같다. - 시작일이 가장 앞선 일정부터 차례대로 채워진다. - 시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다. - 일정은 가능한 최상단에 배치된다. 365일만큼 배열을 만들고, 일정이 있는 구간에 `+1`하여 누적합했다. 빈칸이 있으면 최상단에 배치되기때문에 누적합하여 높이와 길이를 정할 수 있기 때문이다. 일정이 없는 날짜가 나오면 `이전까지 누적했던 길이 * 높이`를 답에 더해주었다. 메모리: 14480KB시간: 136ms언어: Java 11import java.io.*;import java.util.*;publ.. 2024. 5. 19. 이전 1 2 3 다음