2021. 10. 17. 18:00ㆍ카테고리 없음
드디어 대회가 끝났습니다! 참가자 여러분 모두 정말 수고 많으셨습니다.
문제는 이번 주 일요일에 백준 온라인 저지에서 열리는 Open Contest가 종료되면 공개될 예정입니다.
문제는 2-6 조찬우(myyh1234), 2-1 김채완(amsminn), 2-1 남승원(erolf0123)이 출제했습니다.
예상 난이도는 운영진이 예상한 문제의 solved.ac 티어를 의미합니다.
정답 코드들은 더보기에 적었습니다.
목차
- 스물셋(백준 23251번)
- 블록(백준 23252번)
- 자료구조는 정말 최고야(백준 23253번)
- 나는 기말고사형 인간이야(백준 23254번)
- 구름다리 2(백준 23255번)
- 성인 게임(백준 23256번)
- 비트코인은 신이고 나는 무적이다(백준 23257번)
- 밤편지(백준 23258번)
- Celebrity(백준 23259번)
- 최대공약수가 뭔데(백준 23260번)
스물셋
출제자: myyh1234 / 예상 난이도: Bronze 3
알고리즘 분류: 수학
시간복잡도: $O(T)$
모든 23의 배수는 23으로만 이루어진 수의 합으로 나타낼 수 있습니다. 23을 계속 더하면 되기 때문입니다.
또한 23으로만 이루어진 수는 아래처럼 모두 23의 배수입니다.
- $2\,323 = 23\times 101$
- $232\,323 = 23\times 10\,101$
- $23\,232\,323 = 23\times 1\,010\,101$
따라서 23으로만 이루어진 수의 합으로 나타낼 수 있는 모든 수는 항상 23의 배수입니다.
즉, "23으로만 이루어진 수의 합으로 나타낼 수 있는 수" 와 "23의 배수"는 같은 의미이므로, 각 입력에 대해 23 * k를 출력하면 됩니다.
정답 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
|
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(nullptr);
int t, k;
cin >> t;
while (t--) {
cin >> k;
cout << 23 * k << '\n';
}
}
|
cs |
블록
출제자: erolf0123 / 예상 난이도: Bronze 2
알고리즘 분류: 구현
시간복잡도: $O(1)$
정해 외에도 정말정말 다양한 정답이 있을 수 있고, 다양한 부분에서 틀릴 수도 있는 문제입니다..
테트리스처럼 왼쪽부터 꽉 채워진 세로줄은 없어진다고 생각해 봅시다. 이렇게 생각하면 문제의 목표는 모든 블록을 없애는 것이 됩니다. 여기서 몇 가지 관찰이 필요합니다.
- 'ㄴ'자 블록 하나를 없애려면 $1\times 1$ 블록 하나가 필요합니다. 즉, 'ㄴ'자 블록의 개수는 $1\times 1$ 블록의 개수 이하여야 합니다.
- $2\times 1$ 블록 2개가 함께 있으면 결과에 영향을 끼치지 못합니다. 따라서 개수가 홀수라면 $2\times 1$ 블록이 하나 있는 상황과 같고, 짝수라면 $2\times 1$ 블록이 아예 없는 상황과 같습니다.
- $2\times 1$ 블록 하나와 $1\times 1$ 블록이 함께 있는 상황은 $1\times 1$ 블록 하나만 있는 상황과 같습니다.
따라서 'ㄴ'자 블록을 모두 없애고 난 뒤 남은 $1\times 1$ 블록의 수가 짝수라면 답은 "Yes", 아니라면 "No"입니다. 추가적으로 $2\times 1$ 블록의 개수가 홀수라면 $1\times 1$ 블록이 하나 이상 있어야 합니다.
정답 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int t; cin >> t;
while (t--){
int A, B, C; cin >> A >> B >> C;
if(C > A){ cout << "No\n"; continue; }
if(A != 0 && B % 2 == 1) B--;
if((A - C) % 2 == 0 && B % 2 == 0) cout << "Yes\n";
else cout << "No\n";
}
}
|
cs |
자료구조는 정말 최고야
출제자: myyh1234 / 예상 난이도: Silver 2
알고리즘 분류: 구현, 스택
시간복잡도: $O(N)$
풀이 1
번호가 작은 교과서가 번호가 큰 교과서 아래에 깔려 있는 더미가 하나라도 있으면 올바르게 교과서를 나열할 수 없고, 그런 경우가 없다면 항상 올바르게 나열할 수 있습니다. 모든 더미의 책이 번호가 클수록 더 아래에 있다면 순서가 꼬이는 일이 절대 발생하지 않기 때문입니다.
따라서 각 더미의 교과서 번호를 아래부터 순서대로 나열했을 때 내림차순이 아닌 경우가 있다면 "Yes", 아니라면 "No"를 출력하면 됩니다. 더미의 책 정보가 아래부터 주어지므로, 각 더미마다 직전에 입력받은 책 번호가 지금 입력받은 책 번호보다 작은 경우가 없다면 내림차순, 있다면 내림차순이 아니라고 판별할 수 있습니다.
정답 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(nullptr);
int n, m, k, num, bef;
bool chk = true;
cin >> n >> m;
while (m--) {
cin >> k;
bef = n + 1;
while (k--) {
cin >> num;
if (num > bef) {
chk = false;
break;
}
bef = num;
}
if (!chk)
break;
}
cout << (chk ? "Yes" : "No");
}
|
cs |
풀이 2
각 더미의 위에서부터 책을 뽑을 수 있으므로, 더미들을 스택 배열이라고 생각할 수 있습니다.
1번부터 N번 교과서까지 차례대로 살펴보면서 지금 보는 번호가 스택의 꼭대기에 있는지를 검사한 뒤 차례대로 스택에서 뽑는 것을 반복하는 과정에서 어떤 수를 뽑을 수 없다면 답은 No, 모든 수를 뽑을 수 있다면 답은 Yes가 됩니다.
어떤 번호가 스택의 꼭대기에 있는지 판별하는 작업을 모든 스택을 돌아보면서 수행하는 풀이는 $O(NM)$이므로 시간초과입니다. 크기가 N보다 큰 체크 배열을 만든 뒤, i가 어떤 스택의 꼭대기에 있다면 배열의 i번째 값에 해당 스택의 인덱스를, i 위에 어떤 다른 수가 있다면 0을 저장합시다. 이렇게 하면 체크 배열을 참고하여 어떤 원소가 몇 번째 스택의 꼭대기에 있는지 알 수 있고, 스택에서 원소를 뽑은 뒤 새로 꼭대기로 올라온 값에 대해서 체크 배열의 값을 변경하면 계속 체크 배열을 통해 가능 여부를 알 수 있습니다. 1부터 N까지의 각 수를 뽑을 수 있는지 여부를 검사하고 뽑는 작업을 $O(1)$ 에 할 수 있으니 전체 시간복잡도는 $O(N)$이 됩니다.
정답 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include <bits/stdc++.h>
using namespace std;
const int S = 200000 + 10;
int idx[S];
stack<int> stk[S];
int main() {
int n, m, k, num;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> k;
while (k--) {
cin >> num;
stk[i].push(num);
}
idx[stk[i].top()] = i;
}
bool chk = true;
for (int i = 1; i <= n; i++) {
if (!idx[i]) {
chk = false;
break;
}
stk[idx[i]].pop();
if (!stk[idx[i]].empty())
idx[stk[idx[i]].top()] = idx[i];
}
cout << (chk ? "Yes" : "No");
}
|
cs |
나는 기말고사형 인간이야
출제자: myyh1234 / 예상 난이도: Silver 1
알고리즘 분류: 우선순위 큐
시간복잡도: $O(M\log M)$
한 시간에 많은 점수를 얻을 수 있는 과목을 최대한 많이 공부해야 총점을 최대화할 수 있습니다. 또한 각 과목들은 점수가 100점 이상이 되면 더 공부할 필요가 없습니다.
여기까지 알아냈다면 단순히 $b_i$가 큰 과목부터 만점을 받을 만큼 공부하면 된다고 생각할 수 있지만, 한 과목의 점수가 100점을 넘을 수는 없으니 점수가 100점을 넘어가는 순간 비효율적으로 시간을 사용하게 됩니다. 예를 들어 첫 번째 예제를 보면, $b_1$이 $b_2$보다 크지만 무작정 1번 과목을 만점받을 때까지 공부하고 남은 시간에 2번 과목을 공부한다면 1번 과목을 13시간, 2번 과목을 11시간 공부하게 되고, 이때 1번 과목의 마지막 한 시간에는 98점에서 100점으로 점수가 2점 오르기 때문에 그 시간에 3점 올릴 수 있는 과목 2를 공부하는 편이 더 좋습니다.
여기서 남은 과목 중 $b_i$가 가장 큰 과목은 무조건 만점 받기 직전까지 공부하는 것이 가장 효율적이라는 걸 알 수 있습니다. 첫 예제에서 $b_i$가 큰 1번 과목을 100점 받기 직전까지, 즉 98점 받을 때까지 12시간 공부한 이후에는 한 시간 공부하면 2점을 받게 되고, 이때는 2번 과목을 12시간 내내 공부하는 것이 이득입니다.
즉, 아직 만점을 못 받은 과목 중 $b_i$가 가장 큰 과목을 골라 최대한 많이 공부한 뒤, 만점까지 남은 점수가 시간당 오르는 점수로 나누어 떨어지지 않는다면 남은 점수를 새로운 $b_i$로 정하는 식으로 문제를 풀 수 있습니다. 만점을 못 받은 과목 중 $b_i$가 가장 큰 과목을 매번 for문을 돌려 찾으면 시간복잡도가 $O(M^2)$가 되어 시간초과겠지만, 우선순위 큐를 이용하여 $b_i$가 가장 큰 과목을 뽑고, 만점까지 필요한 점수가 시간당 오르는 점수로 나누어 떨어지지 않으면 새로운 $b_i$를 정하고 우선순위 큐에 다시 넣는 방식으로 문제를 푼다면 시간복잡도가 $O(M \log M)$이 되어 시간 안에 문제를 풀 수 있습니다.
정답 코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <bits/stdc++.h>
using namespace std;
int a[200005], b[200005];
int main() {
ios::sync_with_stdio(0), cin.tie(nullptr);
int n, m, ans = 0;
priority_queue<pair<int, int>> pq;
cin >> n >> m;
n *= 24;
for (int i = 1; i <= m; i++) {
cin >> a[i];
ans += a[i];
}
for (int i = 1; i <= m; i++) {
cin >> b[i];
if (a[i] < 100)
pq.emplace(min(b[i], 100 - a[i]), 100 - a[i]);
}
while (n > 0 and !pq.empty()) {
pair<int, int> now = pq.top();
pq.pop();
int now_hour = min(now.second / now.first, n);
ans += now_hour * now.first;
n -= now_hour;
if (now.second - now_hour * now.first > 0) {
now.second -= now_hour * now.first;
now.first = now.second;
pq.push(now);
}
}
cout << ans;
}
|
cs |
구름다리 2
출제자: amsminn / 예상 난이도: Gold 5
알고리즘 분류: 그래프의 표현
시간복잡도: $O(N + M\log M)$
출제자의 풀이: https://kim1109123.tistory.com/22
사전순으로 가장 앞서도록 칠한다는 말은 번호가 작은 집들이 최대한 작은 수의 색으로 칠해지도록 한다는 의미입니다. 즉, 사전순으로 앞서도록 칠하려면 번호가 작은 집부터 보면서 인접한 집들에 없는 가장 작은 색으로 칠해야 합니다.
인접한 집에 없는 가장 작은 색을 시간초과가 나지 않고 구하려면 인접한 집을 모두 살펴보면서 색칠된 집이라면 그 집의 색을 저장한 뒤, 저장된 색을 참고하면서 저장되지 않은 가장 작은 색을 구하면 됩니다. 모든 집을 볼 때마다 인접한 집을 다 살펴보면 $O(N^2)$ 시간복잡도로 시간초과가 나지 않을까? 라고 생각할 수도 있지만, 간선의 관점에서 바라보면 각 간선의 양 끝 점에서 다른 끝 점을 각각 한 번만 보는 것이기 때문에 집을 모두 살펴보는 시간복잡도는 $O(M)$이 됩니다. 두 가지 방법으로 이 작업을 효율적으로 수행할 수 있습니다.
인접한 집의 색을 모두 vector에 넣은 뒤 정렬하고 중복을 제거한 뒤 이 vector를 앞에서부터 보면 vector에 없는 가장 작은 수를 알 수 있습니다. 정렬을 하기 때문에 총 시간복잡도는 $O(M\log M)$입니다. 아래 정답 코드는 이 방법을 사용합니다.
2. set 이용
set에 인접한 집의 색을 모두 저장해 두면 어떤 수가 set에 있는지를 로그 시간에 알 수 있으므로, 1부터 차례대로 살펴보며 set에 없는 가장 작은 수를 찾을 수 있습니다. 시간복잡도는 역시 $O(M\log M)$입니다. 출제자의 정해는 이 방법을 사용합니다.
정답 코드
color 배열에 각 집의 색을 저장했습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <bits/stdc++.h>
using namespace std;
vector<int> gh[101010];
int color[101010];
int main() {
int n, m, a, b;
scanf("%d%d", &n, &m);
while (m--) {
scanf("%d%d", &a, &b);
gh[a].push_back(b);
gh[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
vector<int> near;
for (int j : gh[i]) {
if (color[j] != 0)
near.push_back(color[j]);
}
sort(near.begin(), near.end());
near.erase(unique(near.begin(), near.end()), near.end());
color[i] = 1;
for (int j : near) {
if (j != color[i])
break;
color[i]++;
}
printf("%d ", color[i]);
}
}
|
cs |
성인 게임
출제자: amsminn / 예상 난이도: Gold 4
알고리즘 분류: 다이나믹 프로그래밍
시간복잡도: $O(max(T, 1000000))$
출제자 풀이: https://kim1109123.tistory.com/22
뭔가 다이나믹 프로그래밍의 냄새가 진하게 나는데... 식을 맞게 세우기는 조금 복잡한 문제입니다.
문제에서 요구하는 $X$개의 정사각형이 맞물린 칼날을 만드는 경우의 수는 $D[X][1]$, $X$개의 정사각형이 맞물린 칼날에서 가장 왼쪽의 $1\times 1$ 정사각형이 하나 빠진 모양을 만드는 경우의 수를 $D[X][0]$이라고 부르겠습니다.
1번을 채우는 경우의 수는 $D[7][1]$, 2번을 채우는 경우의 수는 $D[7][0]$이라고 할 수 있겠네요.
정의를 했으니 각 경우의 수를 구해봅시다.
$D[X][0]$을 구하는 경우의 수부터 살펴볼까요?
$D[X][0]$에서 $D[X - 1][1]$을 제외한 나머지 부분을 채우는 경우의 수는 아래 그림처럼 1가지뿐입니다.
$D[X][0]$에서 $D[X - 1][0]$을 제외한 나머지 부분을 채우는 경우의 수는 아래 그림처럼 2가지입니다.
따라서 $D[X][0] = 2\times D[X - 1][0] + D[X - 1][1]$입니다.
$D[X][0]$에서 $D[X - 1][0]$을 뺀 나머지 부분을 채우는 경우의 수가 아래처럼 하나 더 있다고 생각하기 쉽습니다.
하지만 이렇게 다음 $2\times 2$ 정사각형과 겹치는 부분을 $1\times 1$ 으로 채우면 $D[X - 1][1]$에서의 경우와 중복되는 경우가 생길 수 있습니다. 따라서 다음 정사각형과 겹치는 부분을 지금 채울 때는 무조건 $2\times 1$ 으로 채워야 합니다.
같은 원리로 $D[X][1]$을 채우는 경우의 수는 $4\times D[X - 1][0] + 3\times D[X - 1][1]$과 같습니다. 각 경우의 수는 아래 그림을 참고하세요.
$D[1][0] = 3$은 자명하며, $D[1][1] = 7$이라는 것은 예제를 통해 알 수 있습니다.
점화식과 초깃값을 알았으니, $D[1][0]$, $D[1][1]$부터 $D[1\,000\,000][0]$, $D[1\,000\,000][1]$까지 모두 구해둔 뒤 N을 입력받을 때마다 $D[N][1]$을 출력하면 됩니다.
정답 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <bits/stdc++.h>
using namespace std;
long long d[1'000'005][2], MOD = 1e9 + 7;
int main() {
d[1][0] = 3, d[1][1] = 7;
for (int i = 2; i <= 1000000; i++) {
d[i][0] = (d[i - 1][0] * 2 + d[i - 1][1]) % MOD;
d[i][1] = (d[i - 1][0] * 4 + d[i - 1][1] * 3) % MOD;
}
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
printf("%lld\n", d[n][1]);
}
}
|
cs |
비트코인은 신이고 나는 무적이다
출제자: amsminn / 예상 난이도: Gold 4
알고리즘 분류: 다이나믹 프로그래밍
https://kim1109123.tistory.com/22
선린 가을맞이 알고리즘 챌린지 Solution
kim1109123.tistory.com
위 해설에서도 언급하지만, 이런 방식의 다이나믹 프로그래밍을 Knapsack DP 또는 배낭 문제라고 부릅니다. 관심이 있다면 아래 문제를 풀어보는 걸 추천합니다.
https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
밤편지
출제자: myyh1234 / 예상 난이도: Gold 2
알고리즘 분류: 플로이드-와샬 알고리즘
시간복잡도: $O(N^3)$
이슬을 $2^C$방울 이상 마실 수 없다는 의미는 번호가 C 이상인 집은 거쳐갈 수 없고, C 미만인 집은 모두 거쳐가도 상관없다는 의미입니다. $2^1 +2^2 + ... 2^{C-1} < 2^C$ 이기 때문입니다.
플로이드-와샬 알고리즘의 코드를 생각해 봅시다. 3중 for문에서 가장 바깥의 반복문은 거쳐갈 수 있는 정점을 가리켰습니다. 가장 바깥의 반복문의 변수의 값이 x일 때 dist 배열에는 내부의 2중 for문을 돌면서 "1부터 x번 정점까지 거쳐갈 수 있을 때의 최단거리" 가 저장되어 있었습니다. 따라서 집을 정점, 집 사이를 이동하는 시간을 간선의 가중치라고 생각하고 플로이드-와샬 알고리즘을 수행하며 3차원 배열을 이용하여 x번 정점까지 거쳐갈 수 있을 때의 최단거리를 모두 저장해 두면 배열을 참고하며 질문에 답할 수 있습니다.
정답 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <bits/stdc++.h>
using namespace std;
const int MAX = (int)1e9;
int dist[305][305][305];
int main() {
ios::sync_with_stdio(0), cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> dist[0][i][j];
if (!dist[0][i][j] and i != j)
dist[0][i][j] = MAX;
}
}
for (int m = 1; m <= n; m++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
dist[m][i][j] = min(dist[m - 1][i][j], dist[m - 1][i][m] + dist[m - 1][m][j]);
}
}
int C, s, e;
while (q--) {
cin >> C >> s >> e;
cout << (dist[C - 1][s][e] == MAX ? -1 : dist[C - 1][s][e]) << '\n';
}
}
|
cs |
Celebrity
출제자: myyh1234 / 예상 난이도: Gold 1
알고리즘 분류: 비트마스킹, 순열
시간복잡도: $O(5!\times N)$
그래프의 정점의 수가 항상 5개이므로 5개의 정점을 배치하는 $5!$가지 경우를 다 따져보면서 두 번 이상 나오는지 여부를 체크하면 됩니다. 다양한 구현 방법이 있을 수 있지만, 저는 그래프 하나마다 간선이 최대 10개이므로 비트마스킹을 이용하여 그래프를 하나의 정수로 나타냈습니다.
가능한 그래프의 가짓수가 몇 개 되지 않으므로 전처리로 그래프의 가짓수를 모두 구해두고 풀어도 됩니다.
C++에서는 next_permutation 함수를 이용해 모든 경우를 따져보는 작업을 수월하게 할 수 있습니다.
정답 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <bits/stdc++.h>
using namespace std;
const int S = 10000 + 5;
int chk[1024];
vector<int> same[S];
int pair_to_idx(int a, int b) {
if (a > b)
swap(a, b);
switch (a) {
case 1:
return b - 2;
case 2:
return b + 1;
case 3:
return b + 3;
case 4:
return b + 4;
}
}
vector<vector<pair<int, int>>> star;
int main() {
ios::sync_with_stdio(0), cin.tie(nullptr);
int n, e, a, b, idx[6];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> e;
int bit = 0;
star.push_back({});
while (e--) {
cin >> a >> b;
if (a > b) swap(a, b);
bit |= (1 << pair_to_idx(a, b));
star[i].emplace_back(a, b);
}
for (int j = 1; j <= 5; j++)
idx[j] = j;
bool twice = false;
do{
int now = 0;
if (chk[1] == 5 and chk[2] == 1 and chk[3] == 3 and chk[4] == 4 and chk[5] == 2)
now = 0;
for (auto& j : star[i]) {
int tmp = pair_to_idx(idx[j.first], idx[j.second]);
now |= (1 << tmp);
}
if (chk[now]) {
twice = true;
chk[now] = 2;
}
} while (next_permutation(idx + 1, idx + 6));
if (twice)
chk[bit] = 2;
else
chk[bit] = 1;
}
int ans = 0;
for (int i = 0; i < 1024; i++) {
if (chk[i] == 1)
ans++;
}
cout << ans;
}
|
cs |
최대공약수가 뭔데
출제자: amsminn / 예상 난이도: Platinum 4
알고리즘 분류: 뫼비우스 함수, 조합론
https://kim1109123.tistory.com/22
선린 가을맞이 알고리즘 챌린지 Solution
kim1109123.tistory.com