https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 난이도 : 실버 3 태그 : 그리디, 정렬 설명 1, 2, 3, 4 위치에서 물이 흐르고, 길이가 3인 테이프가 있다고 할 때, 위치 1을 테이프를 막기 위해 0.5 ~ 2.5 까지 덮을 수 있습니다. 하지만 위치가 3인 곳은 고치지 못하기에, 위치 3을 막기 위해 2.5 ~ 4.5 까지 덮을 수 있습니다. 즉, 물이 새는 곳의 위치를 오름차순 정렬한 뒤, 가장 처음 물이 떨어지는..
https://www.acmicpc.net/problem/11508 11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net 난이도 : 실버 5 태그 : 그리디, 정렬 설명 3개를 사면 가장 싼 가격의 제품 하나를 무료로 줍니다. 그냥 단순히 내림차순으로 정렬 후, 가장 비싼 물품과 그 다음으로 비싼 물품을 산 뒤, 3번째로 비싼 물품을 공짜로 받고, 4번째로 비싼 물품과, 5번째로 비싼 물품을 산 뒤, 6번째로 비싼 물품을 꽁자로 받는 과정을 반복하여 풀 수 있을 것 같습니다. 소스코드 fun main() ..
https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 난이도 : 플래티넘 4 태그 : 그리디, 정렬 설명 문제 자체는 간단합니다. n과, n개의 숫자가 주어질 때 해당 숫자를 잘 조합하여 가장 큰 수를 만드는 문제입니다. 소스코드 첫 번째 시도 import java.util.StringTokenizer fun main() { val n = readln().toInt() val st = StringTokenizer(r..
https://www.acmicpc.net/problem/15904 15904번: UCPC는 무엇의 약자일까? 첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 www.acmicpc.net 난이도 : 실버 5 태그 : 그리디, 문자열 설명 주어진 문자열로 UCPC라는 약자를 도출할 수 있는지를 판단하는 문제입니다. 초기 아이디어는 리스트를 하나 두고, 사용한 문자열을 하나씩 빼면서 리스트가 비면 도출 가능하다고 판단했었는데, 생각해보니 U - C - P - C 순으로 해야더라고요... 결국 UCPC 중 몇 번째 문자열까지 가능한지 체크할 포인터 변수 하나를 두..
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 난이도 : 골드 5 태그 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐 설명 한 시간대에 동시에 진행중인 강의가 몇 개인지 체크하는 문제입니다. 가장 처음 든 생각은 아무래도 int 배열을 체크해놓고 하나씩 체크해볼까? 생각했지만, 시작, 끝 시간의 범위 (0 ≤ Si < Ti ≤ 109)를 보고 바로 다른 방법을 고민하였습니다. 아무래도 우선순위 큐를 사용해 그리디적으로 풀 수 있을 것 같네요. 위와 같이 그림으로 그려 나타내면 쉬울 ..
https://www.acmicpc.net/problem/17371 17371번: 이사 $(\frac{2}{3}, \frac{1}{3})$으로 이사를 가면 가장 가까운 편의시설은 (0, 1)으로 거리는 $\frac{2\sqrt{2}}{3}$이고, 가장 먼 편의시설은 (-4, 1) 혹은 (4, -3)으로 거리는 둘 다 $\frac{10\sqrt{2}}{3}$이다. 두 거리의 www.acmicpc.net 난이도 : 골드 1 태그 : 그리디, 기하학 설명 다소 삽질을 좀 했던 문제였습니다. 가장 가까운 편의시설까지의 거리와 가장 먼 편의시설까지의 거리의 평균이 최소가 되는 좌표 가장 먼 편의시설까지의 거리는 잘 모르겠지만, 가장 가까운 편의시설까지의 거리는 사실 계산을 하는 로직이 필요하지 않습니다. 바로 편..
https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 난이도 : 골드 3 태그 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐 설명 과제는 마감일이 있고, 과제 하나를 끝내는 데에는 하루가 걸립니다. 과제를 풀 때마다 각기 다른 점수를 얻을 수 있을 때, 점수의 최댓값을 구하는 문제입니다. 어려운 것 같지만 천천히 접근해봅시다. 최댓값을 구하려면, 어떤 숙제를 해야 할까요? 바로 점수가 높은 숙제부터 하는 것입니다. 그럼 숙제를 언제 해야 할까요? 각 숙제는 마감일 안에 언제든지 하면 됩..
https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 이론, 그리디 알고리즘, 그래프 탐색, 깊이 우선 탐색 설명 첫째 열에서 시작해 서로 교차하거나 중첩되지 않으면서 마지막 열로 가는 경로를 찾는 문제입니다. 1번 예제 같은 경우는 최대 두 가지 경로를 그릴 수 있습니다. 2번 예제 같은 경우는 아래와 같이 최대 5개의 경로(파이프 라인)이 있습니다. 파이프라인은 왼쪽에서 오른쪽 방향으로 놓을 수 있으며, 오른쪽 대각선 위, 오..
https://www.acmicpc.net/problem/2720 2720번: 세탁소 사장 동혁 각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다. www.acmicpc.net 난이도 : 브론즈 3 태그 : 수학, 그리디, 사칙연산 설명 줘야하는 동전의 개수가 최소가 되야하는 문제입니다. 그리디 알고리즘의 기초격인 문제인데요. 단순히, 현재 줘야하는 금액에서 25센트 짜리 동전을 최대한 거슬러 주고, 그 다음 10, 그 다음 5, 나머지 1센트 짜리 동전으로 거슬러 주면 됩니다. 소스코드 import java.lang.StringBuilder fun main() = with(System.`in`.bufferedReader()) { val s..