본문 바로가기

Problem Solving/문제풀이

 (89)
백준 21275번 폰 호석만 문제 요약 문자열 A, B가 주어진다. 두 문자열이 각각 A진법, B진법으로 표현되어 있다고 했을 때 10진법으로 바꾼 숫자를 A', B'라고 하자. A' = B' 이면서 A != B인 (A,B)가 정확히 하나 있다면 그 숫자와 A, B를 출력하고 두 개 이상이라면 Multiple, 없다면 Impossible을 출력하자. 이 때, $ 0 \le A', B' \lt 2^{63}$을 만족해야 한다. $ 2 \le A, B \le 36$ 주어지는 문자열의 길이는 최대 70이다. 풀이 어떤 문자열을 $B$진법으로 표현되어 있다고 가정하고 10진법으로 변환하는 것은 문자열의 길이만큼 시간이 걸린다. 따라서, 주어진 두 문자열을 2진법부터 시작해서 36진법까지 전부 바꿔 ..
백준 21214번 Decoration 문제 요약 숫자 $N, K$가 주어진다. 다음을 만족하는 길이가 K인 수열 $s$중에서 모든 원소의 합이 가장 작은 $s$를 찾아서 출력하시오. 만족하는 수열이 없으면 -1을 출력하면 된다. $s_i \neq s_j, i \neq j, 1 \le i,j \le K$ $ 0 \le s_i \lt N$ $\text{for all } 1 \le i \lt K, s_{i+1} \equiv s_i + D(s_i) \bmod N$, 여기서 $D(x)$는 $x$의 약수의 갯수를 말한다. $ 1 \le N, K \le 1,000,000$ 풀이 문제를 푸는 데에 있어서 중요한 관찰은 3번 조건때문에 $s_i$가 정해지면 $s_{i+1}$이 정해져 버린다는 점이다. 그래서 이런 관계를 함수 $f$로 표현해서 $f(x) =..
백준 18527번 All Kill 문제 요약 문제가 n개 주어지고 시간이 t만큼 주어진다. 문제를 푸는 과정은 두 단계로 나뉜다. 풀이가 생각난다. 코딩을 한다. 각 문제 별로 코딩에 걸리는 시간이 다르며, 각 문제의 풀이가 떠오를 확률은 각 분마다 $\frac{1}{\text{남은 분 수}}$이다. 풀이가 떠오르면 바로 코딩을 시작하는데, 항상 풀이가 떠오른 문제들 중에서 번호가 낮은 문제부터 코딩을 한다. 즉, 7번 문제를 코딩 중인데 2번 문제의 풀이가 떠올랐다면 2번 문제의 코딩을 바로 시작한다. 반대로 2번 문제을 코딩하는 도중에 6, 7번 문제의 풀이가 떠올랐다면 2번 문제의 코딩을 끝내고 6, 7번을 순서대로 코딩한다. 이와 같이 문제를 푼다고 했을 때, 모든 문제를 풀되, 코딩 중에 방해받지 않고 모든 문제를 풀 확률을 $..
백준 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 =..

티스토리툴바