링크: https://www.acmicpc.net/problem/12755 2016 전북대학교 프로그래밍 경진대회 A번 비슷한 문제로는 BOJ 1748 - 수 이어 쓰기 1이 있는데, 거기에 조건을 하나 더 얹었다. 앞에서부터 \(N\)번째 자리에 있는 수를 출력하는 것이다. 1부터 \(N\)까지 전부 확인하는 건 시간적으로도 메모리적으로도 무리다. 따라서 탐색 범위를 좁힐 필요가 있는데 이 문제에서는 자리수별로 인덱스를 자르면 좀 낫다. 1자리 수는 1부터 9까지 9개가 있으며, 전부 이어 붙이면 길이가 9이다.2자리 수는 10부터 99까지 90(=99-10+1)개가 있으며, 전부 이어 붙이면 길이가 180(=90*2)이다.3자리 수는 100부터 999까지 900(=999-100+1)개가 있으며, 전부..

[이전 블로그에서 글 옮김] 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..