백준 (227) 썸네일형 리스트형 백준 16923 - 다음 다양한 단어 https://www.acmicpc.net/problem/16923풀이이 문제는 크게 두 가지의 경우로 나눌 수 있다.알파벳이 모두 들어있지 않은 경우이 경우엔 없는 알파벳 중 가장 작은 알파벳을 맨 뒤에 붙이면 된다.알파벳이 모두 들어있는 경우먼저 zyxwvutsrqponmlkjihgfedcba는 사전순 가장 마지막이기 때문에 사전순으로 오는 다음 문자열이 없다. 이런 경우에만 -1을 출력해 주면 된다. 그렇지 않으면 문자열 $s$에서 가장 마지막으로 $s_{i} 왜 나머지 문자를 지우냐면, 문자열의 사전순 비교는 길이가 작은 게 앞으로 오기 때문이다. 정답 코드 - C++더보기#pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")#pragma GCC o.. 백준 30689 - 미로 보수 https://www.acmicpc.net/problem/30689 이 문제는 단순히 "사이클로 들어가는" 노드 중에서 최소 비용을 가진 노드만 택하면 틀렸습니다를 받는다. 문제에 주어진 그래프는 함수형 그래프인데, 이런 경우가 흔히 발생할 수 있기 때문이다. 단순한 사이클 찾기를 통해 그룹을 묶는다면, 그림과 같이 문제 조건에서 고려할 수 있는 유의미한 사이클 외에 1, 2번 노드에서 비용을 고르는 경우가 생길 수 있다. 따라서 문제를 해결하기 위해서는 유효한 사이클만 검출하도록 할 필요가 있다. 그러기 위해서는 그래프의 모든 노드에서 엣지를 따라가되, 이미 방문했지만 종결되지는 않은 노드로 다시 방문하게 되는 순간, 해당 노드부터 시작하는 "유의미한 사이클"을 추적하여 최소 비용을 찾도록 하면 된.. 백준 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이 소수라는 조건이 없으므로 이를 처리하기 어려울 수 있다. 이를 처리하기 위해 양의 정수는 소인수.. 이전 1 2 3 4 ··· 46 다음
