백준/수학 (35) 썸네일형 리스트형 백준 12966 - 턴 게임 2 https://www.acmicpc.net/problem/12966 이 포스트는 12934 - 턴 게임으로부터 얻을 수 있는 통찰을 포함하여 설명하도록 한다.등차수열로의 전환과 등차수열의 합$i$턴에 이긴 사람은 $2 \times i - 1$ 점으로, 이는 모두 홀수이다. 초항을 $a$, 공차를 $d$인 등차수열로 표현할 때, 등차수열의 합은 $S_{n} = \frac{n}{2}(2a + (n - 1)d)$이고,$a = 1, d = 2$이므로 $S_{n} = \frac{n}{2}(2 \times 1 + (n - 1) \times 2)$ = $n^{2}$이다. 따라서, $x + y$는 제곱수가 되어야 한다. $x + y$가 제곱수가 아니라면, 나올 수 없는 경우니 답은 $-1$이다.문제를 $k$ 찾기로 .. 백준 12116 - Uzastopni https://www.acmicpc.net/problem/12116 힌트더보기$a$부터 연속된 $k$개의 정수의 합을 구하려면 다음과 같은 식으로 풀 수 있다. $a \times k + \frac{k \times (k - 1)}{2}$ 그 합이 $N$이 되려면 $N = a \times k + \frac {k \times (k - 1)}{2}$ 를 만족해야 함을 알 수 있다.풀이힌트에서 언급한 식 $N = a \times k + \frac{k \times (k - 1)}{2}$ 를 만족하는 $a$를 구해보도록 하자. 식을 정리하면 $2N = k(2a + k - 1) \rightarrow 2a = \frac{2N}{k} - k + 1$가 되므로 적절한 범위의 $k$에 대해 $2a$가 짝수인 경우를 모두 찾아.. 백준 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.. 이전 1 2 3 4 ··· 7 다음