본문 바로가기

Problem Solving

 (98)
백준 21088번 Remove the Prime 문제 요약 수가 n개 주어진다. 어떤 소수 p와 연속적인 구간[l,r]을 선택할 수 있는데, 해당 구간에 있는 모든 수들이 p로 나눠져야 한다. p와 [l,r]을 골랐으면 해당 구간의 수들에서 소인 수 p를 지운다. $a_l, a_{l+1}, \ldots , a_r$에 대해서 p로 더이상 나눠지지 않을 때 까지 p로 나누는 것과 같다. 두 플레이어가 번갈아가면서 위와 같은 선택을 하는 게임을 진행한다고 하자. 그리고 행동을 취할 수 없으면 지는 게임이다. 두 플레이어가 최적으로 게임을 진행했을 때, 승자를 결정하시오. $ n \le 1000$, $ 1 \le a_i \le 10^{18}$. 풀이 이 문제에 대해서 알고 있는 풀이가 두 개 있는데 코드 짜기가 힘들지만 생각하기 쉬운 풀이부터 소개한다. 먼저..
백준 20940번 시철이가 사랑한 수식 문제 요약 아래 두 수식의 값을 구하면 된다. $$ \begin{gather} \sum_{n=1}^N \sum_{i=1}^n \sum_{j=1}^n (gcd(i,j) \times lcm(i,j)) \\ (\sum_{n=1}^N \sum_{i=1}^n \sum_{j=1}^n gcd(i, j)) \times (\sum_{n=1}^N \sum_{i=1}^n \sum_{j=1}^n lcm(i,j)) \end{gather} $$ N과 K가 주어지는데 N은 최대 100만이고 K는 위의 값들을$\mod K$로 구하라는 뜻이다. K는 소수임이 보장된다. 풀이 먼저 첫번째 식을 보자. $lcm(i,j) = \frac{ij}{gcd(i,j)}$다. 따라서, 시그마 안의 식은 그냥 $ij$다. $$ \begin{aligne..
백준 20938번 반짝반짝 문제 요약 전구 N개가 일자로 놓여있다. 만약 i번째 전구가 고장나면 i번째 전구를 포함하고 i번째 전구와 연결된 오른쪽 전구도 모두 꺼진다. 각 전구가 꺼질 확률과 구간 수 K가 주어진다. N개의 전구를 K개의 연속 구간으로 쪼개려고 한다. 이 때, 켜진 전구의 개수의 기댓값의 최댓값을 계산해야 한다. N은 최대 2500이며, K는 최대 10이다. 풀이 먼저, $C(i,j)$를 [i,j]에서 켜진 전구들의 개수의 기댓값이라고 하자. 그러면 원하는 값은 다음과 같은 DP로 구할 수 있다. $$ \begin{gather} dp(i, j) = \text{첫번째 전구부터 i번째 전구까지를 j개의 구간으로 쪼갰을 때 최댓값} \\ dp(i, j) = \underset{k> N >> K; for(int i=1;i..
백준 20927번 Degree Bounded Minimum Spanning Tree 문제 요약 노드 갯수 N과 간선 갯수 M이 주어진다. 그리고 각 정점의 차수 제한 $b_i$가 주어진다. 차수 제한을 만족하는 스패닝트리 중에서 그 비용이 가장 작은 스패닝 트리를 출력하시오. 차수 제한을 만족하는 스패닝트리가 없다면 NO를 출력하라. N은 최대 10, M은 최대 27이다. 풀이 일단 최대 입력으로 들어왔을 때, 간선을 고르는 경우의 수는 $\binom{27}{9}$로 500만이 조금 안된다. 여기에다가 $M$을 곱해도 시간 내에 들어온다. (스패닝 트리가 되려면 간선을 N-1개 골라야 한다.) 즉, 간선을 고르고 스패닝 트리인지 확인하기 위해서 BFS나 DFS를 해도 시간 내에 충분히 돈다. BFS나 DFS는 $O(N+M)$이다. #include using namespace std; s..
백준 20926번 얼음 미로 문제 요약 가로 세로가 최대 500인 맵이 주어진다. 시작점과 도착점이 주어졌을 때, 도착점에 도착이 가능하다면 최단 시간을, 안되면 -1을 출력하면 된다. 풀이 삼성 A형 같은 느낌의 문제다. 문제에서 주어진 조건을 잘 읽고 그대로 구현을 잘해준 다음에 다익스트라를 돌리면 된다. 미끄러졌을 때, 벽으로 가거나 구멍으로 빠지면 그건 움직일 수 없는 경우이다. 조심하자. 돌에 부딪히거나 도착점에 도착해야만 멈추는 게 가능하다. 모든 점 $(i,j)$에 대해서 위, 오른쪽, 아래, 왼쪽으로 쭉 가면서 돌을 만나면 그 지점과 $(i,j)$를 이동에 드는 시간만큼의 간선으로 이어주면 된다. #include using namespace std; const int MAXN = 505; const int MAXM =..
백준 20925번 메이플스토리 문제 요약 사냥터가 N개 주어진다. 각 사냥터에는 사냥터에 진입하기 위한 최소 경험치 $c_i$와 1분마다 얻는 경험치 $e_i$가 주어진다. 그리고 각 사냥터 간 이동에 필요한 시간도 주어진다. 총 $T$분을 쓸 수 있다고 할 때, 얻을 수 있는 최대경험치를 출력하시오. 사냥터의 개수 N은 최대 200이고, $T$는 최대 1000이다. 풀이 이리저리 생각해볼 수도 있지만 일단 dp를 생각하자. $$ dp[i][j]=\text{i번째 사냥터에서 j분에 얻을 수 있는 최대 경험치}dp[i][j]=\text{i번째 사냥터에서 j분에 얻을 수 있는 최대 경험ㅊ} $$ 이러면 이제 j분에 i번째 사냥터에 있을 때 할 수 있는 선택은 두 종류가 있다. 이 사냥터에서 계속 사냥하거나, 다른 사냥터로 이동하거나. 이..
백준 20924번 트리의 기둥과 가지 문제 요약 트리와 루트노드가 주어진다. 처음으로 자식의 수가 2 이상이 되는 노드를 기가 노드라고 하자. 만약에 그런 노드가 없다면 리프 노드를 기가 노드라고 하자. 문제에서 원하는 것은 루트에서 기가 노드까지의 거리와 기가 노드를 루트로 하는 서브트리에서 기가 노드와의 거리가 가장 먼 노드의 거리를 출력해야 한다. 노드 수 N은 최대 20만이다. 풀이 먼저 기가 노드를 찾아야 한다. 이는 루트 노드에서 부터 dfs를 진행하면서 자식의 수가 2 이상인 노드를 찾으면 dfs를 종료하는 식으로 찾을 수 있다. 기가 노드에서부터 가장 먼 노드를 찾는 것도 위 과정에서 기가 노드의 부모만 잘 저장해뒀다가 dfs를 돌리면 찾을 수 있다. #include using namespace std; const int MA..
백준 20923번 숫자 할리갈리 문제 요약 플레이어가 두 명 있다. 각 플레이어의 카드 더미가 주어진다. 각 플레이어는 번갈아 가면서 본인의 그라운드에 본인의 카드 더미 제일 위에서 카드를 내려놓는다. 카드를 내려놓을 때 이미 그라운드에 카드가 놓여있었다면 이미 놓여있던 카드는 고려하지 않는다. 도중에 특정 조건을 만족하면 그라운드에 있는 카드들을 본인 카드 더미로 들고간다. 도도의 조건은 그라운드에 나와 있는 두 카드 중에 숫자가 5인 카드가 있는 것이고, 수연이의 조건은 그라운드의 나와있는 두 숫자의 합이 5가 되는 것이다. 단 비어있는 그라운드가 있어선 안된다. 도도가 먼저 이 과정을 시작한다. 한 사람이 승리하면 그라운드에 있는 카드들을 본인의 카드 더미 아래에 놓는다. 이런 과정을 반복할 때, 본인의 카드더미가 비게 되면 진다..

티스토리툴바