링크: 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..

확장 유클리드 알고리즘(Extended Euclidian Algorithm)은 유클리드 호제법을 확장한 것이다. $as + bt = gcd(a,b)$을 만족하는 정수 $s$, $t$ 짝을 찾아낼 수 있다. 증명은 생략하고 어떻게 사용하는가를 적어볼까 한다. 초기 조건 $s_0 = 1, s_1 = 0, ~~t_0 = 0, t_1 = 1, ~~r_0 = a, r_1 = b$ 진행 $$ \begin{align} q_i \leftarrow & \lfloor~r_{i-1}~/~r_i~\rfloor & (i \ge 1)\\ r_i \leftarrow & ~r_{i-2} - r_{i-1} \cdot q_{i-1} & (i \ge 2)\\ s_i \leftarrow & ~s_{i-2} - s_{i-1} ..

​중국인의 나머지 정리(CRT; Chinese Remainder Theorem)연립 합동식의 유일한 해를 찾는 정리이다. 예를 들면서 설명과 함께 전개하는 게 가장 이해하기 쉽다. 개념 이해를 위해 연립 합동식이 2개일 때만 생각해보자. $$\begin{cases} x \equiv 3 ~ (mod~ 5)~\dashrightarrow~ (a) \\ x \equiv 4~ (mod~ 7)~\dashrightarrow ~(b) \end{cases}$$ 위 두 합동식 (a), (b)를 모두 만족하는 어떤 정수 $x$는 어떻게 찾을 수 있을까?어떤 수 $x$는 위 두 합동식을 모두 만족하기 위해 (a), (b)의 해를 각각 $A_1$, $A_2$라고 하면 아래의 형태가 된다.$$ x \equiv A_..