https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 도토리가 들어간 상자번호를 구해내는 문제. 간격을 d로 두며, 구간 [a,b] 에서 도토리가 들어가있는 상자의 개수는 min(b,now)/d - a/d +1이다. now 는 내가 정한 상자번호. /d 로 묶어보면 좀 더 자명해지는데, (min(b,now) - a)/d + 1로, b보다 now가 더 작으면 세면 안..

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제에서 제시한 B[K] 가 K번째로 큰 수 이니까 K를 다르게 해석해보자면 B[K] 보다 작거나 같은 수가 K개 있는 것이 된다. 그래서 B[K]를 mid로 잡고 파라메트릭 서치하면서 개수만 세주면 K에 대한 답을 구할 수 있다. B[K] 가 mid로 잡힌거기때문에 파라메트릭 구간의 끝값이 N*N 인줄 알았는데 AC코드까보니까 K도 된다고하는데 왜인지는 모르겠다. ..

아니 이거 왤케 역겨움;; 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 정육면체를 포함..

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사이의 간격이 가장 커서 뺐다는 결론에 도달했고 ..