[BOJ] 랜덤 마라톤 (No. 17930, 11170, 8662, 22232, 30625)
by 구설구설17930
문제
Hanging Out on the Terrace
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 142 118 110 83.333%
문제
스톡홀름의 HiQ 사무실에는 꽤 멋진 옥상 테라스가 있어 회사 파티나 프로그래밍 대회와 같은 이벤트에 자주 사용된다.
하지만, 화재 안전 규정으로 인해 테라스에 동시에 있을 수 있는 최대 인원 수는 L명으로 제한된다. 파티 도중, 사람들이 테라스에 들어오고 나가며, 현재 테라스에 있는 사람 수를 계속 추적하는 것은 매우 번거롭다. 게다가, 사람들은 종종 그룹으로 테라스에 들어오려고 한다. 한 그룹이 테라스에 들어오려 하지만 그들의 추가로 화재 안전 제한을 초과하게 된다면, 해당 그룹은 테라스에 들어가는 대신 내부에서 탁구를 치게 된다.
당신의 작업은, 파티 도중 테라스에 들어가려 시도한 그룹의 크기와 테라스에서 나간 사람들의 수가 주어졌을 때, 테라스에 들어갈 수 없었던 그룹의 수를 계산하는 프로그램을 작성하는 것이다.
입력 형식
첫 번째 줄에는 화재 안전 제한 (1 <= L <= 200)과 이벤트의 수 (0 <= x <= 100)가 주어진다.
그다음 x개의 줄에는 각 이벤트가 주어진다. 각 이벤트는 "enter" 또는 "leave"로 시작하며, 이는 해당 이벤트가 그룹이 테라스에 들어가려는지 아니면 사람들이 테라스를 떠나는지를 나타낸다.
그 뒤에는 정수 (1 <= p <= 200)가 주어지며, 이는 해당 시점에 테라스에 들어오거나 나가는 사람의 수를 나타낸다.
테라스를 떠나는 사람 수는 현재 테라스에 있는 사람 수를 초과하지 않는다.
출력 형식
파티 중 테라스에 들어갈 수 없었던 그룹의 수를 출력한다.
예제 입력 1
4 5
enter 3
enter 2
leave 1
enter 1
enter 2
예제 출력 1
2
예제 설명
최대 4명만 테라스에 있을 수 있다.
처음 3명이 테라스에 들어간다.
이후 2명이 테라스에 들어가려 시도하지만, 총 인원이 3 + 2 = 5로 제한인 4를 초과하기 때문에 들어가지 못한다.
한 사람이 테라스를 떠나 현재 2명이 남는다.
그 사람이 다시 돌아와 총 3명이 된다.
마지막으로 2명이 테라스에 들어가려 시도하지만, 다시 총 인원이 5로 제한을 초과하기 때문에 들어가지 못한다.
따라서 테라스에 들어가지 못한 그룹의 수는 총 2이다.풀이
현재 인원과 최대 인원의 차가 들어오려고 하는 인원보다 작은지를 확인한다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int l, x, cur = 0, ans = 0;
cin >> l >> x;
for (int i = 0; i < x; i++) {
string s;
int p;
cin >> s >> p;
if (s == "enter") {
if (l - cur < p) {
ans++;
} else {
cur += p;
}
} else if (s == "leave") {
if (cur < p) {
ans++;
} else {
cur -= p;
}
}
}
cout << ans;
}
11170
문제
0의 개수
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
3 초 256 MB 7472 5530 4777 75.585%
문제
N부터 M까지의 수들을 종이에 적었을 때 종이에 적힌 0들을 세는 프로그램을 작성하라.
예를 들어, N, M이 각각 0, 10일 때 0을 세면 0에 하나, 10에 하나가 있으므로 답은 2이다.
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 줄에는 N과 M이 주어진다.
1 ≤ T ≤ 20
0 ≤ N ≤ M ≤ 1,000,000
출력
각각의 테스트 케이스마다 N부터 M까지의 0의 개수를 출력한다.
예제 입력 1
3
0 10
33 1005
1 4
예제 출력 1
2
199
0풀이
n과 m 사이에 있는 수들을 string으로 바꾼 뒤 string의 인덱스를 이동하면서 '0'이 있는지 확인한다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while (t > 0) {
t--;
int n, m, ans = 0;
cin >> n >> m;
for (int i = n; i <= m; i++) {
string s = to_string(i);
for (int j = 0; j < s.length(); j++) {
if (s[j] == '0') ans++;
}
}
cout << ans << '\n';
}
}
8662
문제
Szuflady
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 78 39 35 50.725%
문제
Michał은 침실에 n개의 서랍이 있는 서랍장을 가지고 있다. 각 서랍은 특정 길이만큼 앞으로 나와 있다. Michał은 매번 서랍을 더 빼지 않고도 각 서랍에 직접적으로 접근할 수 있기를 원한다.
서랍 i에 직접적으로 접근 가능하다는 것은, 그 위에 있는 모든 서랍들이 그 서랍보다 덜 나와 있어야 함을 의미한다. Michał은 서랍을 오직 밀어 넣는 동작(즉, 서랍 길이를 줄이는 것)만 할 수 있다. 이때 모든 서랍에 직접적으로 접근하기 위해서 최소 몇 개의 서랍을 밀어 넣어야 하는지 궁금해한다.
단, 서랍의 길이가 0이 되면 그 서랍에 접근할 수 없다고 가정하며, 서랍 길이는 항상 정수값이어야 한다.
입력
입력의 첫 번째 줄에는 서랍의 개수 n (1 ≤ n ≤ 10^6)이 주어진다.
두 번째 줄에는 n개의 정수 a1, a2, ..., an (1 ≤ ai ≤ 10^9)이 주어지는데, ai는 위에서부터 i번째 서랍이 앞으로 나와 있는 길이를 의미한다.
출력
출력의 첫 번째 줄에, 모든 서랍에 직접적으로 접근 가능하도록 만들기 위해서 Michał이 최소 몇 개의 서랍을 밀어 넣어야 하는지를 나타내는 정수를 출력한다. 만약 불가능하다면 -1을 출력한다.
예제 입력 1
5
8 4 7 6 8
예제 출력 1
2
힌트
Michał은 첫 번째와 세 번째 서랍을 밀어 넣는다. 예를 들어, 가능한 서랍 길이 상태는 (1, 4, 5, 6, 8)과 같을 수 있다.풀이
가장 아래 서랍부터 탐색하면서 이전 서랍보타 크면 이전 서랍 -1 로 변경한다.
만약 어떤 서랍이 0 이하가 되면 -1을 반환한다.
#include <bits/stdc++.h>
using namespace std;
vector<long long> drawer;
long long ans;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
long long temp;
cin >> temp;
drawer.push_back(temp);
}
for (int i = n - 2; i > -1; i--) {
if (drawer[i] >= drawer[i + 1]) {
ans++;
drawer[i] = drawer[i + 1] - 1;
if (drawer[i] < 1) {
cout << -1 << '\n';
return 0;
}
}
}
cout << ans << '\n';
return 0;
}
22232
문제
가희와 파일 탐색기
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1.5 초 512 MB 1155 385 282 32.829%
문제
가희는 jo_test 폴더에 들어와 있습니다. 가희는 jo_test에 있는 파일 N개를 아래 기준에 따라 정렬하려고 합니다.
파일명 (FILENAME) 사전순으로
파일명 (FILENAME)이 같다면 가희가 설치한 OS에서 인식하는 확장자가 붙은 것이 먼저 나오게
1과 2로도 순서를 결정할 수 없다면, 파일 확장자 (EXTENSION) 사전 순으로
파일 N개를 문제에서 설명하는 정렬 기준에 따라 정렬해 주세요. 사전순의 기준은 아스키 코드 순입니다.
입력
첫 번째 줄에 jo_test 폴더에 있는 파일 개수 N과 가희가 설치한 OS에서 인식하는 파일 확장자의 개수 M이 공백으로 구분되어 주어집니다.
2번째 줄부터 N+1번째 줄까지 FILENAME.EXTENSION 형식의 문자열이 주어집니다. 여기서 .은 온점을 의미합니다.
FILENAME은 소문자와 숫자로만, EXTENSION은 소문자로만 이루어져 있습니다.
그 다음 줄 부터 가희가 설치한 OS에서 인식하는 파일 확장자 (EXTENSION) M개가 주어집니다.
출력
기준에 따라 정렬된 결과를 출력해 주세요.
제한
1 ≤ N ≤ 2×105
1 ≤ M ≤ 2×105
파일 확장자와 파일명의 길이는 10을 넘지 않습니다.
입력으로 주어지는 FILENAME.EXTENSION 꼴의 N개는 중복되지 않습니다.
가희가 설치한 OS에서 인식하는 파일 확장자 M개는 중복되지 않습니다.
예제 입력 1
5 3
abc.jpeg
abc.jpg
foo.yolo
bar.cpp
bar.maltise
jpg
cpp
maltise
예제 출력 1
abc.jpg
abc.jpeg
bar.cpp
bar.maltise
foo.yolo
1번 예제에 대한 설명입니다.
먼저 FILENAME 순으로 정렬했을 때 아래와 같이 세 개의 그룹으로 나뉩니다.
abc.jpeg abc.jpg
bar.cpp bar.maltise
foo.yolo
가희가 설치한 OS에서 jpeg는 인식하지 못하고, jpg는 인식하는 확장자이므로, 두 번째 기준에 따라 정렬하면 아래와 같습니다.
abc.jpg
abc.jpeg
bar.cpp bar.maltise
foo.yolo
아직 bar.cpp와 bar.maltise의 순서는 결정되지 못하였습니다. 세 번째 정렬 기준에 따라서, 확장자 사전순으로 정렬하면 아래와 같습니다.
abc.jpg
abc.jpeg
bar.cpp
bar.maltise
foo.yolo
예제 입력 2
5 1
vvv.busan
dongdaegu.miryang
gupo.busan
train1225.mugunghwa
trainer.jpg
jpg
예제 출력 2
dongdaegu.miryang
gupo.busan
train1225.mugunghwa
trainer.jpg
vvv.busan
숫자는 소문자보다 아스키 코드 값이 작습니다.풀이
파일명을 읽어와 확장자를 분리한 후, 확장자가 인식되는지 여부를 확인하여 정렬한다.
- 파일명 사전순
- 인식된 확장자가 있는 파일이 먼저
- 확장자 사전순
unordered_set을 사용하여 시간초과를 피한다.
#include <bits/stdc++.h>
using namespace std;
int n, m;
unordered_set<string> recognized_extensions;
bool _sort(const pair<string, string>& a, const pair<string, string>& b) {
if (a.first != b.first) return a.first < b.first;
bool a_recognized = recognized_extensions.count(a.second);
bool b_recognized = recognized_extensions.count(b.second);
if (a_recognized != b_recognized) return a_recognized > b_recognized;
return a.second < b.second;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
vector<pair<string, string>> files(n);
for (int i = 0; i < n; i++) {
string full_name;
cin >> full_name;
int pos = full_name.find('.');
files[i] = {full_name.substr(0, pos), full_name.substr(pos + 1)};
}
for (int i = 0; i < m; i++) {
string ext;
cin >> ext;
recognized_extensions.insert(ext);
}
sort(files.begin(), files.end(), _sort);
for (const auto& file : files) {
cout << file.first << '.' << file.second << '\n';
}
return 0;
}
30625
문제
댄스타임
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 1024 MB 457 160 146 40.669%
문제
호영이는 기대하던 WooJeans의 팬미팅에 가게 되었다. 팬미팅의 하이라이트인 댄스타임에서는 마지막 라운드를 통과한 팬에게 사인 앨범을 주는데, 열혈팬 호영이도 사인 앨범을 받기 위해 열심히 춤 연습을 하고 있다.
댄스타임은 N개의 라운드로 이루어져 있으며, 각 라운드에는 WooJeans의 리더 우진이 바라보는 방향에 따라 올바른 춤을 춰야 한다. 댄스타임의 각 라운드에서 올바른 춤을 췄다는 것은 아래와 같이 춤을 추는 것을 뜻한다.
우진이 앞을 보고 춤을 추면 호영이는 우진과 같은 춤을 춰야 한다.
우진이 뒤를 보고 춤을 추면 호영이는 우진과 다른 춤을 춰야 한다.
댄스타임에서는 최대 한 번까지 올바르지 않은 춤을 추더라도 해당 라운드를 통과할 수 있다. 즉, 두 번 이상 올바르지 않은 춤을 추면 즉시 해당 라운드에서 떨어지게 된다.
호영이가 마지막 라운드까지 통과하여 사인 앨범을 받을 수 있는 경우의 수를 구해보자. 이때, 적어도 하나의 라운드에서 호영이가 추는 춤의 종류가 다르면 다른 경우이며, WooJeans의 열혈팬 호영이는 우진이 출 모든 춤을 알고 있다.
입력
첫째 줄에 댄스타임의 라운드 개수 N, 우진이 출 춤 종류의 개수 M이 공백으로 구분되어 주어진다. (1 <= N <= 100,000), (1 <= M <= 100)
둘째 줄부터 N+1번째 줄까지 각각의 줄에 우진이 추는 춤의 종류와 우진이 춤을 추는 동안 바라보는 방향을 나타내는 두 정수 A_i,
B_i가 공백으로 구분되어 주어진다. (1 <= A_i <= M), (0 <= B_i <= 1)
우진은 B_i가 0이면 앞, 1이면 뒤를 바라보고 춤을 춘다.
출력
첫째 줄에 호영이가 사인 앨범을 받을 수 있는 경우의 수를 소수 1,000,000,007로 나눈 나머지를 출력하라.
예제 입력 1
4 4
1 0
3 1
2 0
4 1
예제 출력 1
69풀이
DP 문제이다.
dp 벡터에 값이 있다면 그 값을 가져다 쓰고, 없으면 틀렸는지 여부에 따라 경우의 수를 구한다.
중간중간 나눠야 하는건 좀 귀찮음
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'007;
int N, M;
vector<long long> dance;
vector<vector<long long>> dp;
long long count(int pos, int flag) {
if (pos == N) return 1;
if (dp[pos][flag] != -1) return dp[pos][flag];
if (flag == 1) {
dp[pos][flag] = (count(pos + 1, 1) * dance[pos]) % MOD;
} else {
dp[pos][flag] = (count(pos + 1, 1) * (M - dance[pos]) % MOD +
count(pos + 1, 0) * dance[pos] % MOD) %
MOD;
}
return dp[pos][flag];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
dance.resize(N);
for (int i = 0; i < N; i++) {
long long a, b;
cin >> a >> b;
if (b == 0) {
dance[i] = 1;
} else {
dance[i] = M - 1;
}
}
dp.assign(N, vector<long long>(2, -1));
cout << count(0, 0) << '\n';
return 0;
}'Algorithm > BOJ' 카테고리의 다른 글
블로그의 정보
공부중임
구설구설