백준 (225) 썸네일형 리스트형 백준 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이 소수라는 조건이 없으므로 이를 처리하기 어려울 수 있다. 이를 처리하기 위해 양의 정수는 소인수.. 백준 27915 - 금광 https://www.acmicpc.net/problem/27915 문제에서 가장 중요한 점은 한 기업은 최대 2개의 노드만 소유할 수 있다는 것이다. 왜냐하면 3개 이상의 노드를 점유한다고 했을 때 각 노드가 홀수의 거리를 유지한다고 해도 양 끝의 노드의 거리가 짝수가 되기 때문이다. 따라서 각 기업은 무조건 홀수 레벨에서 짝수 레벨로만 연결할 수 있고, 이는 색 $R, B$로 구성된 이분그래프로 표현할 수 있다. 이렇게 이분그래프를 만들었을 때 $max(|R|, |B|)$가 정답이 된다. 정답 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162.. 백준 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이 나타나면 같은 단계를 반복하지 않는다는 문제 조건에 모순이 되기 때문이다. 따라서 .. 이전 1 2 3 4 ··· 45 다음