-
[BOJ] 8091 : Petrol
8091 : Petrol 풀이 KOI 주유소 문제에 자동차 연로탱크의 capacity가 추가된 버전(?) (사실 주유소 문제가 기억 안 나서 맞는지는 모름) 암튼 비슷하다. 시작점에서 끝점까지의 거리가 100만밖에 되지 않는다는 사실! 아하! 그렇다면 시작점으로부터의 거리를 인덱스로 삼는 배열을 하나 만들 수 있겠군! 오, 그럼 자동차를 한 칸씩 움직이면서 연료 탱크 최대값과 가능한 범위 내의 최소 기름값을 잘 관리하면 풀 수 있겠군!! 음… 근데 문제 분류를 어떻게 해야할지 모르겠군 코드 #include <cstdio> #include <queue> using namespace std; int...
-
[BOJ] 8098 : Lecture Halls Reservation
8098 : Lecture Halls Reservation 풀이 회의실 배정이랑 비슷하게 생겼다. 오… 이거 데이터 생겨먹은 게 끝나는 시간을 기준으로 정렬해주고 싶게 생겼다. 시간의 최대 범위가 3만이므로, 각각의 시간에 대해, 해당 시간까지의 최대 해를 계산해줄 수 있다. 약간 다이나믹스러운 느낌으로 d[time] = max(d[time], d[start]+end-start) 주어진 구간의 양 끝점만 보고 삭 긁어주면 된다. 시간 범위가 3만보다 (엄청) 크다면 세그트리 등등을 이용해서 풀어줄 수 있겠다. 코드 #include <cstdio> #include <algorithm> using namespace std; int n, r, d[30003]; pair<int, int>...
-
[BOJ] 8983 : 사냥꾼
8983 : 사냥꾼 풀이 어떤 동물을 사냥할 수 있는지 판단해야한다. 그러기 위해선 어떤 동물에서 가장 가까운 어떤 사냥대를 찾아야 한다. 동물의 y좌표는 모든 사냥대에 대해 절대적인 반면, x좌표는 사냥대에 대해 상대적이다. 그러므로 동물의 x좌표와 사냥대의 x좌표만 비교해서 O(1) 또는 O(log n)의 시간에 가장 가까운 사냥대를 찾을 수 있다. O(1)은 적당히 반복문을 잘 굴리면 되고 O(log n)은 적당히 이분탐색 같은 걸 사용하면 된다. (안 해봤지만 아마 될 거다 ㅎ) 코드 #include <cstdio> #include <algorithm> using namespace...