문제 14469번: 소가 길을 건너간 이유 3N마리 소들이 각각 도착 시간과 검문에 걸리는 시간이 주어질 때, 한 번에 하나씩만 검문을 받으며 모든 소가 농장에 입장하는 데 필요한 최소 시간을 구하는 문제이다.www.acmicpc.net풀이 입력받은 소들을 (도착 시간, 걸리는 시간) 형태로 저장한다. 소들을 도착 시간(arrive) 기준으로 정렬한다. 정렬된 순서대로 소가 검문을 받는다. 이전 소가 끝나기 전이면 기다려야 한다. 이전 소가 끝난 후에 도착한 소는 즉시 검문을 시작한다. sum은 "마지막 소가 검문을 마친 시간"을 의미한다. 정렬된 소를 순서대로 보며 sum = max(sum, arrive) + duration을 해준다. 여기서 max(sum, arrive)이란 현재 소가 도착하기 전..

문제 1246번: 온라인 판매달걀 N개를 팔려고 한다. M명의 잠재 고객이 있고, 각 고객이 낼 수 있는 최대 금액 Pi가 주어진다. 한 고객당 한 개만 팔 수 있고, 원하는 가격을 정했을 때 얻을 수 있는 최대 수익의 가격과 수익을 구하는 문제이다.www.acmicpc.net 풀이 먼저 낮은 가격부터 판매 가격 후보로 삼기 위해 모든 고객이 제시한 가격을 정렬한다. 각 가격 price를 판매 가격으로 사용할 경우, 그 가격 이상 지불할 수 있는 고객의 수는 현재 인덱스부터 끝까지의 사람 수인 m - idx다. 단, 팔 수 있는 최대 개수는 n개이므로 m - idx 코드 fun main() { val (n, m) = readln().split(' ').map{ it.toInt() } v..

문제 1235번: 학생 번호여러 학생의 학번(문자열)이 주어질 때, 끝에서부터 k글자만 잘라서 모든 학번이 서로 다르게 되는 최소의 k를 구하는 문제입니다.www.acmicpc.net 풀이 각 문자열의 접미사들을 왼쪽에서 한 글자씩 줄여가며 비교한다. i번째 글자부터 끝까지의 문자열(접미사)들을 모두 모아 보았을 때,중복되는 접미사가 없다면 더 짧게 잘라도 구분이 가능하므로 다음 칸으로 이동한다. 그러나 어느 시점에서 접미사 중복이 발생하면, 그 이후로는 더 줄일 수 없으므로 그 위치를 기준으로 필요한 최소 길이를 계산한다. 코드 fun main() { val list = List(readln().toInt()) { readln() } val length = list[0].length ..

문제 2417번: 정수 제곱근정수가 주어질 때, 그 수의 제곱근을 구하는 문제이다. q² ≥ N인 가장 작은 정수 q를 출력한다.www.acmicpc.net 풀이 이 문제는 정수 n이 주어졌을 때 x^2 >= n을 만족하는 가장 작은 정수 x를 찾는 것이다. 이를 위해 이분 탐색(Binary Search) 을 사용한다. 범위는 0 ~ n 까지이며, 중간값 mid 를 잡고 만약 mid * mid >= n 이라면 → 더 작은 정답이 있을 수 있으므로 end = mid - 1 그렇지 않다면 → 더 큰 값이 필요하므로 start = mid + 1이 된다. 이 과정을 반복하면 최종적으로 start가 조건을 만족하는 최소의 값이 된다. 여기서 주의할 점은 mid * mid 가 매우 커질 수 있으므로 Doub..

문제 15970번: 화살표 그리기직선 위에 위치한 N개의 점에 색깔이 지정되어 있다. 각 점 p에서 동일한 색을 가진 점 q 중에서 p와의 거리가 가장 가까운 점으로 화살표를 그릴 때, 모든 점에서 시작하는 화살표의 길이 합을 구하는 문제이다.www.acmicpc.net 풀이 같은 색의 좌표를 정렬한 뒤, 각 점에서 가장 가까운 옆 점과의 거리만 더해주면 전체 최소 거리가 된다. 각 점은 색을 가지고 있고, 같은 색의 점들끼리만 연결해야 한다. 한 점에서 연결할 수 있는 점은 오직 양 옆에서 가장 가까운 점 하나뿐이며 그 중에서도 더 가까운 쪽과의 거리만 더해주면 된다.색은 최대 5000까지 주어지므로, 색마다 따로 리스트를 만들어 좌표를 저장한다. 각 색의 점들을 정렬해야 양쪽 이웃을 정확히 찾을 ..