kth990303의 코딩 블로그

재밌는 문제가 뭐있을까 둘러보다가 발견한 문제. 마침 우리 학교에서 푼 사람이 아무도 없기도 해서 랭작용으로도 좋을 듯 해서 풀어보았다. 문제는 아래와 같다. https://www.acmicpc.net/problem/11877 11877번: 홍수 용량이 정확히 X인 히스토그램을 만들 수 없다면 첫째 줄에 -1을 출력해라. 그렇지 않다면 용량이 X가 되는 히스토그램의 열 h1, h2, …, hN를 출력해라. 그러한 방법이 여러 개가 있다면 아무 것이 www.acmicpc.net 문제 해석이 조금 껄끄러울 수 있는데, 쉽게 말해서 1~N까지의 높이로 이루어진 기둥들만으로 히스토그램을 만들되, 양옆 높이가 자신 높이보다 낮을 경우 물이 새므로 불가능하며, 맨 끝쪽에는 물이 없어야 한다는 소리다. 의식의 흐름 ..

개인적으로 꽤 어렵게 느껴졌기 때문에 풀고난 후 티어를 보고 깜짝 놀랐다. 내가 정점/간선 인덱스를 헷갈리게 하는 유형에 약해서 그런진 모르겠지만, 나는 G1~P5 급이라 생각한다. 하지만 그만큼 배울점도 많았던 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/20553 20553번: 다오와 디지니의 데이트 첫 줄에 두 정수 $N$과 $T$가 주어진다. ($2 \le N \le 100\,000$, $1 \le T \le 10^{9}$) 두 번째 줄에 $N$개의 정수가 공백으로 구분되어 주어지며, $i$번째 수는 $h_i$를 의미한다. ($-10^9 \le h_i \le 10^9$, $h_1 = 0$) www.acmicpc.net 얘들아 근데 너네 데이트는 어떻게 하니..

쉬울 줄 알았는데 생각보다 헤맨 문제. 관찰의 중요성을 일깨워주는 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/3088 3088번: 화분 부수기 상근이는 K512 뒤쪽에 화분 N개를 놓았다. 태완이는 이 화분을 모두 부수어 버리려고 한다. 화분은 한 줄로 놓여져 있으며, 세 정수가 쓰여져 있다. 태완이가 화분 하나를 깼을 때, 그 화분에 쓰여 www.acmicpc.net 주의할 점은 인접한 오른쪽 화분만 깨뜨리는 것이 아닌, 오른쪽에 있는 화분들 중 숫자가 하나라도 겹치는 화분들은 모조리 깨뜨리는 것이다. 문제를 잘못 읽지 않도록 주의하자. 의식의 흐름 및 해설 처음에는 문제를 잘못 읽어서 인접한 화분만 비교하여 유니온파인드로 같은 숫자일 경우 merge해주어..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 이 문제 역시 예전에 해결했던 문제이다. 그러나 복습 겸 다시 한 번 풀어보았다. 의식의 흐름 및 해설 역시 골드 난이도 답게 호락호락하지 않았다. 확실한 건 점수를 많이 얻을 수 있는 과제를 많이 할 수록 좋다는 점이다. 당연해보이지만, 여기까지 접근했다면 30%는 맞는 셈. 그런데 최대한 많은 과제를 하기 위해선 마감기한이 최대한 앞에 있는 것을 하는 게 좋지 않을까? 그렇다고 마감기한 순으로 정렬하면 더 높은 점수를 받을 수 있는 과제..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 너무나도 유명한 문제이다. 아주 예전에 풀었었지만, 복습 겸 다시 한 번 풀어보았다. 굉장히 유명하기도 하고, 시리즈 문제도 매우 많은 편이다. 의식의 흐름 및 해설 회의를 최대한 많이 하기 위해서는, 최대한 빈 회의시간이 없도록 해야 한다. 따라서 항상 최적해 풀이를 사용하는 그리디로 접근하면 될 듯하다. 그럼 이제 여기서 여러가지 생각이 들 것이다. "회의 시간이 짧은 순으로 정렬해야되나?", "회의 시작 시각이 이른 순?", "회의 종료 시각이 빠른 순?" 정답은 바로 "회의 종료 시각이 빠른 순으로 정렬하..