백준/수학 (33) 썸네일형 리스트형 백준 2378 - 불필요한 수 https://www.acmicpc.net/problem/2378 문제에 주어진 N에서 일부 값에 대해 수열의 원소 $R_{i}$가 등장하는 횟수를 계산해 보면 이는 파스칼의 삼각형과 동일한 형태를 가짐을 파악할 수 있다. 그러면 길이가 N일 때 수열의 원소가 최종적으로 등장하는 횟수를 이항계수로 표현하면 $$Count(R) = \{ {N - 1 \choose 0}, {N - 1 \choose 1}, ..., {N - 1 \choose N - 1} \}$$ 으로 나타낼 수 있다. 그러면 N까지의 원소에서 이항계수를 구했을 때 나머지 M에 나눠떨어지는지 확인하면 되는데 $MAX(M) = 10^{9}$이고 M이 소수라는 조건이 없으므로 이를 처리하기 어려울 수 있다. 이를 처리하기 위해 양의 정수는 소인수.. 백준 12994 - 이동 3-2 https://www.acmicpc.net/problem/12994 문제에 음수 방향으로도 갈 수 있다는 조건이 있어 어떤 값의 조합으로 되어있는지 찾기 어렵다. 다만 더하거나 빼는 수는 $3^{k}$으로만 이루어졌다는 부분에 주목할 수 있는데, 이는 x와 y에 배분하는 경우를 2진법으로 나타낼 수 있다는 것이다. x와 y를 빼지 않고 더하는 경우만 있다고 해보자. 예시를 들어 $sum = x + y$라고 할 때 $sum = 11111_{3}$라고 하자. 그러면 $x = 11100_{3}, y = 00011_{3}$으로 나타낼 수 있다. x와 y의 자릿수에는 1이 중복으로 나타나면 안 되는데, 어떤 자릿수에 중복으로 1이 나타나면 같은 단계를 반복하지 않는다는 문제 조건에 모순이 되기 때문이다. 따라서 .. 백준 31002 - 그래프 변환 https://www.acmicpc.net/problem/31002 문제에 주어진 변환을 직접 손으로 해보자. 그러면 다음 사실을 발견할 수 있다. 차수를 $deg$이라고 할 때, 첫 변환에서 정점이 될 간선에서 연결된 기존 $G$의 정점으로 하여금 각각 연결된 간선이 $deg - 1$개만큼 존재하여 총 $2(deg - 1)$ 만큼의 간선이 새로 생기고 역시 새로운 차수가 된다. 이때 총 간선의 개수는 악수 정리에 의해 $\frac {VE}{2}$가 된다. 간선이 어떻게 증가하는지 파악했으니 위 계산을 $K$번 반복해주면 답을 구할 수 있다. 정답 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474.. [ICPC] 백준 28152 - Power of Divisors https://www.acmicpc.net/problem/28152힌트 1더보기문제에서 유효한 해가 존재할 때 $f(n)$의 값은 충분히 작다.힌트 2더보기$n^{f(n)} = x$라는 조건에 의해 $x$는 어떤 수의 거듭제곱으로 이루어져야만 함을 확인할 수 있다. 힌트 1과 힌트 2에서 언급한 사실을 종합했을 때, 후보를 빠르게 추릴 수 있는 방법이 있는가?풀이더보기$2^{64} > 10^{18}$이므로, $f(n)$이 가질 수 있는 최댓값을 64로 잡는다. 그러면 1부터 64까지 반복을 돌면서 $1 \leq i \leq 64$에 대해 어떤 정수 $a$가 $a^{i} = x$인지 $a$에 대해 이진탐색을 시행하여 확인할 수 있다. $a^{i} = x$를 만족하는 a를 찾을 경우, $f(a) = i$인지.. 백준 27437 - 분수찾기 2 https://www.acmicpc.net/problem/27437힌트더보기문제에 그려진 테이블을 유심히 보자. 위와 같이 구분한다고 했을 때 패턴을 찾아낼 수 있는가?풀이더보기위 힌트에서 주어진 테이블을 대각선으로 나눴다. 그러면 우리는 각 대각선에서 발견할 수 있는 중요한 성질을 다음과 같이 정리할 수 있다. 각 대각선에 속한 수들의 집합을 $D_{1}, D_{2}, D_{3}, ...$으로 부르며 원소의 갯수는 $1, 2, 3, ...$이다. 이때 $D_{i}$의 원소인 $\frac{y}{x}$에서 $MAX(x, y) = i$이다. 우리는 $\sum_{i = 1}^{n}\nolimits i \leq X$를 만족하는 $i$의 최댓값을 파라메트릭 서치로 찾아낼 수 있다. 그리고 대각선을 문제의 규칙에.. 이전 1 2 3 4 ··· 7 다음
