L.O.K

1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000 www.acmicpc.net ◎ 문제풀이 풀이를 알면 굉장히 쉬운 문제인데... 쉬운 풀이까지 가기란 참으로 어려운 것 같다. 변수(range)를 하나 선언한다. 변수(range)는 현재 설치된 널빤지 정보를 갖는다. range가 9이면 현재 9까지 널빤지가 설치된 것이다. 처음에는 설치된 널빤지가 없으니 range는 0이다. 다음 물웅덩이가 3(start)부터 10(end)까지라고 가정해보자. start(3)가 range(0)보다 크므로 range를 start(3..

https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net ◎ 문제풀이 [백준] 13334 - 철로 문제 링크: https://www.acmicpc.net/problem/13334 알고리즘 실력이 나름 된다고 근본없는 자만심에 가득... blog.naver.com 위 포스팅을 참고하여 풀었다. 아무리 생각해도 시간복잡도가 O(N²) 풀이만 생각났는데 최소Heap을 이용하면 O(NlogN) 시간복잡도가 가..

https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net ◎ 문제풀이 선을 입력 받고 선을 시작점을 기준으로 내림차순 정렬한 뒤 하나씩 가져와 비교해본다. 그럼 경우는 3가지가 있다. 파란선 : 기존선 연두선 : 새로운 선 1) 완전히 겹치는 경우 완전히 겹치는 경우는 무시하고 넘어간다. 2) 부분이 겹치는 경우 부분이 겹치면 시작점은 그대로이고 종료점이 새로운 선의 종료점까지 늘어난다. 3) 안 겹치는 경우 시작점을 기..