체크무늬 공대생

. 문제)https://www.acmicpc.net/problem/11032소설가인 김대전은 여러 파일로 나눠진 소설을 합쳐 최종적으로 하나의 파일로 합치려 한다.두 개의 파일을 합칠 때 필요한 비용이 두 파일 크기의 합이라 가정한다.예를 들어 C1,C2,C3,C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 40,30,30,50 이라 하자.첫 번째 방법으론 C2와 C3을 합친 뒤, C1과 합친다. 마지막으로 C4를 합친다.이 때의 비용은 60+100+150 = 310이다. 두 번째 방법으론 C1과 C2를 합치고, C3와 C4를 합친 뒤 두 파일을 서로 합친다.이 때의 비용은 70+80+150=300이다.따라서 두 번째 방법이 좀 더 저렴하고, 위처럼 각 파일의 크기가 주어졌을 때 이들..

. 문제) https://www.acmicpc.net/problem/1300 세준이는 크기가 NxN인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j]=ixj 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 NxN이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. (배열 A와 B의 인덱스는 1부터 시작한다.) . 접근) 가장 직관적인 방법은 단순히 B를 정렬 후, B[k]를 반환하는 것이라 볼 수 있다. 그러나 이 경우 quick sort를 기반으로 하는 파이썬의 라이브러리 sort 함수를 사용해도 O(NlogN)이기에 시간초과가 발생한다. 따라서 이 문제는 정렬 알고리즘을 사용하는 게 아닌, 이중탐색(Binary Search) 알고리즘의 사용이 핵심이다. 그렇다면 이중탐색의 탐색할 ..

. 문제)https://www.acmicpc.net/problem/211 수직선 상에 있는 N개의 집 좌표와 설치할 공유기 개수 C가 주어진다. 이후 가장 인접한 두 공유기 사이의 거리를 최대로 하여 설치하려 한다. 이를 만족하게 설치했을 때 가장 인접한 두 공유기 사이의 거리를 출력하시오.Input) Output) 5 3 3 1 2 8 4 9. 접근)처음 이 문제를 보고 든 생각은, 양 끝 지점에 무조건 공유기를 설치 후 가장 긴 구간의 중간 지점마다 공유기 설치를 하면 되는 거 아닌가? 였다. 그러나 모든 지점에 집이 존재하는 것이 아니므로 정확히 2등분이 될 수 없고, 매 경우마다 N개의 집 사이 거리를 계산해줘야 하기에 시간초과가 난다. 따라서 이 문제는 주어진 정보를 통해 적절히 이분탐색을 해야..