아니 이거 왤케 역겨움;; https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net Hmaxhp 를 파라메트릭 서치해주면 된다. 숫자 범위부터 해서 상당히 역겨운 문제인데 몇가지 들어보자면 1. 나이브하게 싸우는걸 시뮬레이션하면 TLE를 받음 2. 파라메트릭 최고범위가 123456 * 1e12 Hmaxhp ll mid = (s+e)/2; if(s>e) return s; ll Hmaxh..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 처음 보고 뇌절이 심하게 왔었는데, 지문에서 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 를 보고 저 "가장 인접한 두 공유기 사이의 거리" 가 파라메트릭으로 얻고자 하는 값일거라는 킹리적 갓심을 하고 짜서 AC받았다. 가장 인접한 두 공유기 사이의 거리는 아무리 길어도 (오른쪽끝 - 왼쪽끝) 의 길이보다 길 수 없다..

파라메트릭 서치는 몇번을 해도 ㄹㅇ 이 뇌절을 막을수가 없음 어떻게하는지 아직도 잘 ㅁㄹ겠다. https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 블루레이의 녹화 가능한 길이에 따라서 True/False 여부가 갈리는 이분탐색 문제였다. M개로 쪼개는건 그냥 나이브하게 O(N) 에 처리가능. 파라메트릭이 상수가 많이붙어서그렇지 O(log1e9) 상수시간에 처리가 되고있는데 TLE를 받진 않을거같다. 더보기 #include using namespace st..

분할정복 컷 https://www.acmicpc.net/problem/2339 2339번: 석판 자르기 하나 이상의 불순물과 보석 결정체로 이루어진 석판을 여러 조각으로 나누어 가공해서, 보다 높은 가치를 얻을 수 있도록 만들려고 한다. 이때, 높은 가치의 석판을 만들기 위해서는 석판을 여 www.acmicpc.net 보석 결정이 자르는 선 위에 위치하면 안된다는 조건을 놓쳐서 고민좀함. 선을 하나 그어주면 가로선인 경우로 예시를 들 때 선 윗부분의 직사각형 하나 ( 다음에 세로선을 그어야함 ) 선 아랫부분의 직사각형 하나 ( 다음에 세로선을 그어야함 ) 그래서 그어야할 선 방향을 매개변수로 하나 더 넣어주는 재귀함수를 짜면 분할정복이 됨. 모든 점에 대해서 가로세로로 선 그어서 쪼개는경우 다 생각해줘도..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 지문부터 풀이과정까지 찔리는 문제... 과제를 가장 효율적으로 해결하려면 과제를 마지막날에 몰아서 하는게 가장 좋다. 몸으로경함하고있다. 그런데, 같은 날짜에 진행하려고 "다투는" 여러 과제의 경우에는, 가장 많은 점수를 받는 과제를 해결하는것이 당연히 효율이 좋다. 그래서 점수순으로 정렬해주고 해당 점수를 받을 과제를 처리할 날짜를 최대한 미뤄주면 정답이 된다. 더보기 #include using namespace std; vector v;..

백준 재활 겸 KOI 준비 겸 라이(kks227)님의 알고리즘 강의를 밀고 있다. 그리디 밀면서 오늘 푼 G5. https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 일단 입력을 보고 센서 좌표가 일직선으로 안들어와서 정렬부터 해줬다. 정렬 하고 보니 테스트케이스에서 3과 6 사이에 연결이 없어야 정답이 나오겠다는 생각이 들었다. 왜 3과 6 사이로 직관했나 생각해보니 3과 6사이의 간격이 가장 커서 뺐다는 결론에 도달했고 ..