2020. 7. 14 에 쓴 글
1번 문제
https://www.acmicpc.net/problem/17614
[문제 요약]
3 6 9 게임에서 박수치는 횟수를 구하는 문제다.
3 6 9게임은 알다시피 1부터 순서대로 외치는데 만약 현재 숫자에 3, 6 혹은 9가 들어가면 그 갯수만큼 박수를 치는 게임이다.
정수 N(1 ≤ N ≤ 10^6)이 주어지고 N까지 369 게임을 진행할 때의 박수치는 횟수를 구하여 출력하는게 목표다.
[풀이]
- int f(int n) : n안에 3, 6 혹은 9가 몇 개 들어가있는지 반환하는 함수.
f(n)은 n의 각 자리수 digit이 3, 6 혹은 9인지 체크하여 카운트 하는 방식으로 구현한다.
- 메인함수에서 1부터 N까지 for문을 돌리며 각 숫자에 대한 f(n)을 카운트한다.
함수 f의 경우 인자로 들어오는 n의 digit의 최대 갯수가 6이므로 시간 복잡도 염려는 안해도 괜찮고
메인함수의 for문의 경우 1부터 N까지 돌리기 때문에 O(N)이다.
[코드]
#include <iostream>
using namespace std;
int f(int n) {
int ret = 0;
while (n) {
if (n % 10 == 3 || n % 10 == 6 || n % 10 == 9)
ret += 1;
n /= 10;
}
return ret;
}
int main() {
int n, ans = 0;
cin >> n;
for (int i = 1; i <= n; i++)
ans += f(i);
cout << ans;
return 0;
}
2번 문제
https://www.acmicpc.net/problem/17615
[문제 요약]
공들이 일렬로 나열되어 있는데 이때 공은 각각 빨간공이거나 파란공이다. (공의 총 갯수 N은 1 ≤ N ≤ 500,000)
이때 공을 옮겨서 같은 색 공이 인접하게 모이도록 만드는 최소 이동 횟수를 구하라.
공을 움직이는 규칙은 다음과 같다.
- 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.
- 옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.
[풀이]
한 가지 색깔의 공만 움직일 수 있으므로 공을 옮기는 방식이 총 4가지가 있다고 생각했다.
-
모든 빨간공을 오른쪽으로 옮기기.
-
모든 빨간공을 왼쪽으로 옮기기.
-
모든 파란공을 오른쪽으로 옮기기.
-
모든 파란공을 왼쪽으로 옮기기.
이 4가지 방식의 이동 횟수 중 최소 이동 횟수가 답이 될 것이다.
각 방식의 이동 횟수를 구하는 방법은 비슷하니 1번 방식만 예시로 들겠다.
초기 공 배열을 balls라는 string에 받았다고 했을 때,
모든 빨간공을 오른쪽으로 옮기려면 먼저 가장 오른쪽에 있는 빨간공부터 맨 오른쪽으로 옮기는게 최선일 것이다.
balls의 맨 마지막부터 탐색하면서 빨간공이 나올 때 그보다 먼저 탐색 된 파란공이 존재했다면 카운트를 하는 방식으로 1번 방식의 최소 이동 횟수를 구할 수 있다.
각 방식의 시간 복잡도는 O(N)이므로 시간초과는 나지 않는다. (1 ≤ N ≤ 500,000)
[코드]
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int f(int n) {
return n > 0;
}
int main() {
int n;
string str;
cin >> n >> str;
long long ans = -1;
//R이 왼쪽으로
long long k, a;
k = a = 0;
//R이 왼쪽으로
for (int i = 0; i < str.length(); i++) {
if (str[i] == 'B') {
k++;
}
else {
a += f(k);
}
}
ans = a;
a = k = 0;
//B가 왼쪽으로
for (int i = 0; i < str.length(); i++) {
if (str[i] == 'R') {
k++;
}
else {
a += f(k);
}
}
ans = min(ans, a);
a = k = 0;
//R이 오른쪽으로
for (int i = str.length() - 1; i >= 0; i--) {
if (str[i] == 'B') {
k++;
}
else {
a += f(k);
}
}
ans = min(ans, a);
a = k = 0;
//B가 오른쪽으로
for (int i = str.length() - 1; i >= 0; i--) {
if (str[i] == 'R') {
k++;
}
else {
a += f(k);
}
}
ans = min(ans, a);
cout << ans;
return 0;
}3번 문제
https://www.acmicpc.net/problem/17616
[문제요약]
N명의 학생이 있는데 그 중 X번 학생의 등수를 알고 싶다.
M번의 질문을 통해 유추해야하는데 질문은 입력한 두 학생 중 어느 학생이 더 잘했는지만 알려준다.
이때 M개의 질문을 통해 알 수 있는 X번 학생의 가장 높은 등수와 가장 낮은 등수를 구하여라.
[풀이]
각 질문에서 a번 학생이 b번 학생보다 잘했다는 정보가 주어지면 그래프(graph)를 두 개 만들어서 G1에는 a --> b를 G2에는 b-->a를 생성한다. (이러면 최종적으로 생성된 G1과 G1은 서로 전치(transpose)관계 일 것임.)
이렇게 만들고 나면 G1에서 x부터 시작하여 인접 노드들을 전부 방문하게 되면 방문 한 다른 노드의 갯수는 x보다 확실히 못한 학생의 수가 될 것이다.
그리고 G2에서 x부터 시작하여 인접 노드들을 전부 방문하게 되면 방문 한 다른 노드의 갯수는 x보다 확실히 잘한 학생의 수가 될 것이다.
여기서 구해진 x보다 확실히 못한 학생의 수로 x번 학생이 가능한 가장 낮은 등수를 구할 수 있고
x보다 확실히 잘한 학생의 수로 x번 학생이 가능한 가장 높은 등수를 구할 수 있다.
[코드]
4번 문제
https://www.acmicpc.net/problem/17617
[코드]
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int n, R, m;
vector<int> v;
vector<int> lens;
vector<int> moves;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> R >> m;
v.resize(n);
lens.resize(n);
moves.resize(n * 2 + 1);
for (int i = 0; i < n; i++)
cin >> v[i];
sort(v.begin(), v.end());
for (int i = 0; i < n; i++) {
lens[i] = (v[(i + 1) % n] - v[i] + m) % m;
}
for (int i = 0; i < n; i++) {
moves[i] = moves[i + n] = lens[i] - R * 2;
}
int s = 0, ans = 0;
for(int i = 0; i < moves.size(); i++) {
s += moves[i];
if(s < 0) s = 0;
ans = max(ans, s);
}
cout << (ans + 1) / 2;
return 0;
}