링크: https://www.acmicpc.net/problem/15686 문제 설명 마지막 줄에 다 요약되어있다. 도시에 있는 치킨집 중에서 최대 \(m\)개를 골라야한다.문제 조건에서 치킨집의 개수는 최대 13개이고, 도시에 있는 치킨집 \(k\)개 중에 \(m\)개를 고르는 경우의 수는 $$C(k, m) = \frac{k!}{m!(k-m)!}$$숫자가 작아서 많아봐야 1500개가 좀 안되므로 치킨집을 선택하는 모든 경우의 수를 시도해 볼만 하다. 정해진 \(m\)개의 치킨집마다 모든 사람들의 집에 도달하는 최소 거리를 사람이 사는 집 기준으로 저장해둔다. 즉, 어떤 조합에 대해 \(j\)번 집은 가장 가까운 치킨집과의 거리를 저장하고 있다. 매 조합마다 모든 거리를 구하면 오버헤드가 심하므로 미리 ..

[이전 블로그에서 글 옮김] https://www.acmicpc.net/problem/2022 https://uva.onlinejudge.org/...&problem=1507 \(a, b, c\) 가 주어지면 \(k\) 를 구해내는 문제이다. 피타고라스로 A, B를 구해서 기울기를 구하고, 두 직선의 교점 방정식을 이용했다. 그리고 교점의 y 위치가 \(c\) 가 되는 순간을 구하도록 이분 탐색을 했다. 우선 a가 포함된 직선을 g(x), b가 포함된 직선을 f(x)라 한다면 아래와 같은 정보가 나온다. \( \begin{cases} A = \sqrt{a^2 - k^2} \\ B = \sqrt{b^2 - k^2} \end{cases} \) \( \begin{cases} f(x) = \frac{B}{k}x..

링크: https://www.acmicpc.net/problem/2887 모든 행성을 터널로 연결할건데, 그 비용의 합이 최소가 되게 만드는 최소 스패닝 트리 문제이다. 문제는 \(N\)이 너무 커서, 행성 사이의 간선을 전부 살피는 건 힘들다는 것이다. 두 행성 A와 B의 거리를 \(min(|x_A - x_B|, |y_A - y_B|, |z_A - z_B|)\) 로 정의했기 때문에 어떤 행성에서 가장 가까울 행성의 후보가 확 줄어든다. 행성 A에서 가장 가까운 행성 B는 \(|x_A - x_B|\)가 최소이거나 \(|y_A - y_B|\)가 최소이거나, \(|z_A - z_B|\)가 최소인 것 3개 중 하나이다. \(x, y, z\)마다 정렬하면 된다.

링크: https://www.acmicpc.net/problem/2718[이전 게시글로부터 글 옮김]2x1 크기의 타일로 4xN 크기의 타일을 채우는 경우의 수를 구하는 문제이다.문제를 작은 문제로 쪼개야하는 데 발상보다는 과정이 쉽게 떠오르지 않아서 해결하는 데 오랜 시간이 걸렸다.2xN 타일 크기의 문제와 똑같이 왼쪽부터 1줄씩 채워나가면서 완성해나간다. 하지만 이 문제는 높이가 4N이기 때문에 1줄을 채울 때 여러 개의 경우가 나온다. [그림 1] 한 줄의 상태를 비트로 표현할 때의 정수 외의 경우(1010 이나 0001 등의 형태)는 나올 수 없다. 왜냐하면 "이전의 줄의 모든 칸은 채워져있다."라는 가정에서 나타나는 상태이기 때문이다. 이 가정이 성립하지 않으면 타일은 채워질 수 없다. [그림 ..

문제링크: https://www.acmicpc.net/problem/9373복도에 센서들이 있고 센서들을 피해 복도를 통과할 수 있는 가장 큰 원의 반지름을 구하는 문제이다. 복도의 너비가 주어지고, 각 센서들의 좌표 x, y와 반지름 r이 주어진다.처음에는 센서와 센서 사이에 존재할 수 있는 원들로 어떻게 MST를 잘 만들면 되지 않을까했는데, 가장 큰 원의 반지름을 구하기가 힘들었다. 하루 정도 계속 틀리고 고민하고를 반복하다 솔루션을 찾아봤다. 솔루션을 보자마자 와 이게 뭐지 싶었다. 이렇게 풀 수도 있구나 신기했다.풀이최소 신장 트리 문제는 맞았고 원과 원 사이의 끼인 원으로 어떻게 하는 것도 맞았다. 근데 최종형태가 이런 식이었다.양쪽 벽을 큰 집합이라고 생각하고 두 집합이 연결될 때까지 MST..

문제 링크 : http://119.201.123.184/30stair/sumofinte/sumofinte.php 정답 코드 중에서 실행 시간이 644ms로 1위다. 이럴 날이 별로 없어서 캡쳐 주륵..문제수열의 길이 N과 질문의 수 Q가 주어지는 데, 둘 다 N, Q sum = L.sum + R.sum