아니 이거 왤케 역겨움;; 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/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net 처음에 그냥 문자열 길이 긴순으로 적당히 나눠보려했는데 aaaaaaaa 뭐 이런 테스트케이스보고 안될거같다고 깨달아버림 dp[k] 를 k-1번째 인덱스까지 문자열을 A에 포함되는 문자열로 만들수 있는지 여부로 정합시다. 그럼 다음 A.length() 개 문자가 서로 똑같을때 dp[k+A.length()] = 1 로 만들어 줄 수 있겠지요 이 과정을 반..

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

kks227님 그리디 정주행 완료 마지막문제라 그런지 까다로웠음. 그리디에 있기보단 얜 분할정복으로 빼야할거같은데 ㅁㄴㅇㄹ https://www.acmicpc.net/problem/1493 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net 암튼 이 문제는 매우 친절하게도 모든 상자가 2^k 꼴이라 큰 상자는 더 작은 상자 8개로 분해될수 있다. 그래서 무조건 큰 상자를 많이 넣는게 이득이므로, 최대한 큰 박스를 하나 우겨넣고 남은 입체도형을 7등분해서 k*k*k 정육면체를 포함..