https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 로직 자체는 떠올리기 쉬웠다. i번째 비행기가 1~gi 까지 도킹할 수 있을 때, gi부터 차례대로 보면서 자리가 남아있으면 채우면 된다. 즉, 도킹할 수 있는 구간중 게이트 번호가 가장 큰 수를 먼저 고르면 가장 많은 비행기를 도킹할 수 있다. 만약 그렇지 않으려면, 다른 순서로 도킹하는 방법이 위 방법보다 더 많은 비행기를 도킹시킬 수 있음을 보이면 된다. 도..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 이 문제는 해답이 너무 뻔했다. 왼쪽에서 오른쪽으로 가는 경로는 여러개 있다. 문제는 한번 지나간 점은 다시 지날 수 없다는 것인데, 이 점이 핵심이 된다. 경로가 서로 겹쳐질 수 없기 때문이다. 따라서 경로를 하나의 실로 표현을 하자면, 위부터 차곡차곡 쌓아나가야 경로를 최대한 많이 만들 수 있다. 하나라도 겹쳐지는 순간 미래에 경로를 만들 때 문제가 될 수 있기 때문이다. 결론적으로 시작점을 맨 위부터 아래방..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전www.acmicpc.net도저히 어떻게 풀어야할지 감을 못잡았다. 찾아보니 페이지 교체 알고리즘과 관련이 있다는 것을 알았다.  Belady algorithm페이지 교체 알고리즘이란 메모리에 페이지를 효율적으로 올리기 위해 나왔다.페이지를 메모리에 올리는데 비용이 많이 들기 때문이다.   물론 메모리에 몇 종류의 페이지를 올려놓고, 같은 페이지가 나오면 메모리에서 가져다 쓰면 된다.문제는 메모리에 올라와 있는 페이지 말고 새로..

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 이 문제의 핵심은 무게들의 합으로 만들 수 없는 무게들 중 가장 작은 값을 원한다는 것이다. 즉, 굳이 모든 무게들의 조합을 구하지 않아도 됨을 암시하고 있다. 작은 무게들의 조합부터 따져야하기 때문에 무게를 기준으로 추들을 먼저 정렬하자. 먼저 누적합으로 접근해보자. 0번째 추부터 k번째 추까지 만들 수 있는 무게의 조합들을 0부터 k까지의 합으로 알 수 있을까? 그럼 0번째 추의 무게가 1, 1번째 추의..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 냅색이긴 한데.. 느낌이 달랐다. 이 문제의 핵심은 가방 하나에 넣을 수 있는 보석들 중, 가장 가치가 높은 보석을 넣어야한다는 것이다. 먼저 떠올린 해법은 가방 하나에 보석 전체를 순회하면서 가장 가치가 높은 것을 넣는 것이었지만, 이는 O(N*K)이고 N과 K는 둘다 300,000이 최대이므로 TLE가 난다. 가방을 하나씩 잡고 검사..