백준 BOJ 15794번 : Count
문제 난이도 : Silver I
알고리즘 분류 : 두 포인터, 이분 탐색
길이 N인 수열이 주어질 때 a_i + a_j와 M의 차이의 절댓값이 가장 작게 하는 a_i + a_j 값을 구하고, 그러한 (a_i, a_j) 쌍이 몇 개나 존재하는지를 구하는 문제이다.
경우의 수를 구하는 문제이므로 수열의 순서는 답에 영향을 주지 않는다.
따라서 정렬을 수행한 뒤 두 포인터로 M과 차이가 가장 작은 a_i + a_j의 값을 구해줄 수 있다.
이제 경우의 수를 구해주어야 하는데, 이는 이분 탐색을 이용하여 a_i + a_j 값이 앞서 구한 최소 diff 값을 만족하는 경우를 구해주면 된다.
diff 값은 차이의 절댓값을 의미하므로 차이가 +diff인 경우와 -diff인 경우를 모두 고려해주어야 한다.
이 때 diff = 0이면 부호를 고려할 필요가 없으므로 적절히 예외 처리를 해준다.
생각보다 실수할 수 있는 부분이 많은 문제이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
int M; cin >> M;
sort(v.begin(), v.end());
int l = 0, r = N-1, diff = INT_MAX;
while(l < r) {
diff = min(diff, abs(v[l] + v[r] - M));
if(v[l] + v[r] < M) l++;
else r--;
}
int ans = 0;
for(int i=0; i<N; i++) {
ans += upper_bound(v.begin()+i+1, v.end(), -v[i] + M + diff)
- lower_bound(v.begin()+i+1, v.end(), -v[i] + M + diff);
if(diff != 0) ans += upper_bound(v.begin()+i+1, v.end(), -v[i] + M - diff)
- lower_bound(v.begin()+i+1, v.end(), -v[i] + M - diff);
}
cout << ans << "\n";
}
백준 BOJ 11423번 : Primes
문제 난이도 : Silver II
알고리즘 분류 : 에라토스테네스의 체, 이분 탐색
여러 테스트케이스에 대한 a, b 값이 주어질 때 a 이상 b 이하의 소수의 개수를 출력하는 문제이다.
이 때 b는 1,000만 이하이다.
최댓값이 1,000만 이하이므로 에라토스테네스의 체를 이용하여 1,000만 이하의 모든 소수를 구해둘 수 있다.
그 다음 모든 소수들에 대해 a ~ b 범위에 드는 소수들의 개수를 구하면 되는데, 이 과정에서 시간 초과가 발생할 수 있으므로 양단 경계값을 이분 탐색으로 찾아주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
vector<bool> prime(10000001, true);
prime[1] = false;
for(int i=2; i*i<=10000000; i++)
for(int j=2; i*j<=10000000; j++) prime[i*j] = false;
vector<int> v;
for(int i=2; i<=10000000; i++)
if(prime[i]) v.push_back(i);
int a, b;
while(cin >> a >> b) {
int l = 0, r = v.size()-1, x = v.size()-1;
while(l <= r) {
int m = (l + r)/2;
if(v[m] >= a) {
x = min(x, m);
r = m - 1;
}
else l = m + 1;
}
l = 0, r = v.size()-1;
int y = 0;
while(l <= r) {
int m = (l + r)/2;
if(v[m] <= b) {
y = max(y, m);
l = m + 1;
}
else r = m - 1;
}
cout << y - x + 1 << "\n";
cout << "\n";
}
}
백준 BOJ 19554번 : Guess the number
문제 난이도 : Silver III
알고리즘 분류 : 이분 탐색 (+ 인터랙티브)
N이 주어지고 1 ~ N 사이의 자연수를 답으로 할 때, up or down으로만 답을 찾아내는 인터랙티브 문제이다.
쉽게 말해 이분 탐색을 인터랙티브로 구현하는 문제이다.
left = 1, right = N으로 잡고 mid = (left + right)/2로 하여 mid 값이 답인지를 물어보고, up down에 따라 범위를 조정하는 과정을 반복해주면 된다.
졸려서 그런지 left right 값의 조정을 반대로 설정해놓고 계속 버퍼를 잘못 비워서 틀렸나 하면서 엉뚱한 곳을 고치고 있었다..
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
int l = 1, r = N;
while(l <= r) {
int m = (l + r)/2;
cout << "? " << m << endl;
int x; cin >> x;
if(x == 0) {
cout << "= " << m << endl;
break;
}
if(x < 0) l = m + 1;
else if(x > 0) r = m - 1;
}
}
백준 BOJ 6010번 : Music Notes
문제 난이도 : Silver II
알고리즘 분류 : 누적 합, 이분 탐색
N개의 음표가 차례대로 지속되는 시간이 주어지고, M개의 쿼리에 대해 특정 시간 값이 주어질 때 해당 시간에 연주되고 있던 음표의 번호를 구하는 문제이다.
시간은 음표의 지속 시간들의 누적 값이므로 음표들의 지속 시간에 대한 누적 합 배열을 구해준다.
그 다음 M개의 쿼리에 대해 시간을 입력받아 이분 탐색으로 해당 시간이 포함되는 최소 번째 구간을 구해준다.
이 때 음표는 0초부터 연주가 되기 시작하므로, 반대로 입력받은 시간을 1초 늘린 뒤 해당 값이 포함되는 최소 번째 구간을 찾아주는 방식을 사용하면 편리하다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(N+1);
for(int i=1; i<=N; i++) {
int x; cin >> x;
v[i] = v[i-1] + x;
}
while(M--) {
int x; cin >> x;
x++;
int l = 1, r = N, ans = N;
while(l <= r) {
int m = (l + r)/2;
if(v[m] >= x) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
cout << ans << "\n";
}
}
백준 BOJ 16401번 : 과자 나눠주기
문제 난이도 : Silver II
알고리즘 분류 : 이분 탐색
N명의 사람에게 M개의 과자를 최대 길이로 동일하게 나눠줄 때 그 최댓값을 구하는 문제이다.
이분 탐색을 활용하여 과자의 길이를 먼저 가정하고 N명 이상에게 나눠줄 수 있는지를 체크하여 그 최댓값을 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(M);
for(int i=0; i<M; i++) cin >> v[i];
int l = 1, r = INT_MAX, ans = 0;
while(l <= r) {
int m = (l + r)/2;
int sum = 0;
for(int i=0; i<M; i++) sum += v[i] / m;
if(sum >= N) {
ans = max(ans, m);
l = m + 1;
}
else r = m - 1;
}
cout << ans << "\n";
}
백준 BOJ 11663번 : 선분 위의 점
문제 난이도 : Silver III
알고리즘 분류 : 정렬, 이분 탐색
1차원 좌표 위의 점 N개와 선분 M개의 끝 점이 주어진다고 할 때, 각 선분 위에 있는 점의 수를 구하는 문제이다.
먼저 점의 위치를 오름차순으로 정렬해준 뒤에, 각 선분에 대해 양 끝 점 안에 들어오는 점의 범위를 이분 탐색하면 된다.
점들 중 선분 내에 들어오는 가장 왼쪽 점의 번호를 이분 탐색 해주고, 선분 내에 들어오는 가장 오른쪽 점의 번호를 이분 탐색 해주어 개수를 세어줄 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end());
while(M--) {
int a, b; cin >> a >> b;
int l = 0, r = N-1, x = INT_MAX, y = INT_MIN;
while(l <= r) {
int m = (l + r)/2;
if(v[m] >= a) {
x = min(x, m);
r = m - 1;
}
else l = m + 1;
}
l = 0, r = N-1;
while(l <= r) {
int m = (l + r)/2;
if(v[m] <= b) {
y = max(y, m);
l = m + 1;
}
else r = m - 1;
}
if(x == INT_MAX || y == INT_MIN) cout << 0 << "\n";
else cout << y - x + 1 << "\n";
}
}
백준 BOJ 14170번 : Counting Haybales
문제 난이도 : Silver III
알고리즘 분류 : 정렬, 이분 탐색
위의 문제와 완전히 동일한 문제이다.
풀이 코드도 완전히 동일하다.
백준 BOJ 1072번 : 게임
문제 난이도 : Silver III
알고리즘 분류 : 이분 탐색
게임 횟수와 승리 횟수가 주어질 때, 소숫점 아래를 버린 승률이 변하기 위해서는 앞으로 몇 게임을 연승해야 하는지를 구하는 문제이다.
게임 횟수가 a, 승리 횟수가 b라면 b * 100 / a로 정수 승률을 구할 수 있다.
이분 탐색을 활용하여 (b + m) * 100 / (a + m) 값이 위의 승률과 다른지를 체크해가면서 최소 정답을 탐색해주면 된다.
이분 탐색 결과값이 오른쪽 끝으로 붙으면 승률이 절대 변하지 않는 것이므로 -1을 출력해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int a, b; cin >> a >> b;
int x = b * 100 / a;
int l = 1, r = INT_MAX, ans = INT_MAX;
while(l <= r) {
int m = (l + r)/2;
int y = (b + m) * 100 / (a + m);
if(x != y) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
if(ans != INT_MAX) cout << ans << "\n";
else cout << -1 << "\n";
}
백준 BOJ 10263번 : Opening Ceremony
문제 난이도 : Silver III
알고리즘 분류 : 그리디
N개의 높이가 주어진 블럭들 중 하나의 블럭을 제거하거나, 특정 높이 이상인 블럭들의 높이를 1 줄인다고 할 때 모든 블럭을 제거하기 위한 최소 연산 횟수를 구하는 문제이다.
먼저 특정 높이는 항상 1로 잡는 것이 최선임을 알 수 있다.
이제 최소 연산이 나올 수 있는 경우를 생각하면, 다음의 3가지가 있다.
1. 모든 블럭을 하나씩 제거한다. (이 때 연산 횟수는 N)
2. 모든 블럭을 1층씩 제거한다. (이 때 연산 횟수는 a_max)
3. 내림차순 정렬을 한 뒤 특정 번째 블럭까지는 하나씩 제거하고, 그 뒤 블럭들은 1층씩 제거한다.
1, 2, 3을 모두 구해 그 중 최솟값을 답으로 얻어주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end(), greater<int>());
int ans = min(N, v[0]);
for(int i=1; i<N; i++) {
ans = min(ans, i + v[i]);
}
cout << ans << "\n";
}
백준 BOJ 6236번 : 용돈 관리
문제 난이도 : Silver II
알고리즘 분류 : 이분 탐색
N일 간 사용하는 돈이 주어지고, 이들 중 특정 금액만큼을 필요한 날마다 (남은 돈을 넣은 상태로) 뽑아서 사용한다고 할 때, M번 이하로 뽑아서 쓸 수 있는 최소 금액을 구하는 문제이다.
(문제에서는 정확히 M번이라고 하였는데 필요하면 입금과 인출을 추가로 반복할 수 있기 때문에 사실상 M번 이하라고 보면 된다.)
문제의 핵심은 돈이 모자랄 경우 남은 금액을 입금한 다음 다시 뽑아서 사용한다는 것이므로, 답이 될 수 있는 금액은 N일 간의 사용 금액 중 최댓값 이상이 되어야 한다.
따라서 left 값을 v_max, right 값은 적당히 크게 잡아서 이분 탐색을 수행해주면 답을 얻을 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(N);
int Max = 0;
for(int i=0; i<N; i++) {
cin >> v[i];
Max = max(Max, v[i]);
}
int l = Max, r = INT_MAX, ans = INT_MAX;
while(l <= r) {
int m = (l + r)/2;
int cnt = 0, cur = 0;
for(int i=0; i<N; i++) {
while(v[i] > cur) {
cur = m;
cnt++;
}
cur -= v[i];
}
if(cnt <= M) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
cout << ans << "\n";
}
백준 BOJ 2792번 : 보석 상자
문제 난이도 : Silver II
알고리즘 분류 : 이분 탐색
M 종류의 보석(a_1 ~ a_M)을 같은 사람에게는 같은 종류만 나눠주어 N명에게 나누어줄 때, 보석을 가장 많이 받은 사람의 갯수가 최소가 되도록 할 때 그 최솟값을 구하는 문제이다.
이분 탐색을 활용하여 보석을 몇 개씩 나눠줄지를 먼저 정하고, 그 다음 그 때 가장 보석을 많이 받은 사람의 개수를 구하여 최솟값을 갱신해주는 방식으로 풀이하면 된다.
a개의 보석을 b명한테 최대한 균일하게 나누어줄 때 보석을 가장 많이 받은 사람의 보석의 개수는 (a - 1)/b + 1로 간단하게 나타낼 수 있음을 알아두자.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(M);
for(int i=0; i<M; i++) cin >> v[i];
int l = 1, r = INT_MAX, ans = INT_MAX;
while(l <= r) {
int m = (l + r)/2;
int sum = 0;
for(int i=0; i<M; i++) sum += (v[i] - 1)/m + 1;
if(sum <= N) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
cout << ans << "\n";
}
백준 BOJ 1614번 : 영식이의 손가락
문제 난이도 : Silver III
알고리즘 분류 : 구현
손가락을 1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, ...의 순서로 카운트한다면 a번째 손가락을 b번까지만 사용할 수 있다고 할 때 수를 몇까지 셀 수 있는지 구하는 문제이다.
먼저 손가락 번호로 매긴 수열은 주기가 8인 수열임을 알 수 있고, 1번 손가락과 5번 손가락은 1번씩 카운트 되며 나머지 손가락은 2번씩 카운트 됨을 알 수 있다.
따라서 두 경우를 나누어 조건문을 작성해주고, 주기인 8 단위로 나누어 카운트를 해준 뒤 나머지는 직접 카운트 해주는 식으로 구현해주면 된다.
8으로 나눈 나머지 개수만큼을 카운트하는 부분의 구현이 간단하지는 않은데, v[8] = {1, 2, 3, 4, 5, 4, 3, 2}처럼 놓고 반복문을 돌려서 세어주면 조금 수월하다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int a, b; cin >> a >> b;
int ans = 0;
if(a == 1 || a == 5) {
ans += b*8;
if(a == 5) ans += 4;
}
else {
ans += (b/2) * 8;
int v[8] = {1, 2, 3, 4, 5, 4, 3, 2};
for(int i=0; i<8; i++) {
if(v[i] == a) {
if(b % 2 == 0) break;
else b--;
}
ans++;
}
}
cout << ans << "\n";
}
백준 BOJ 17124번 : 두 개의 배열
문제 난이도 : Silver III
알고리즘 분류 : 이분 탐색
수열 A와 B에 대해, 새로운 수열 C의 원소 c_i를 a_i와 가장 가까운 B의 원소의 값으로 정의할 때, 수열 C의 원소들의 합을 구하는 문제이다.
수열 B의 순서는 답에 영향을 주지 않으므로, 수열 B를 오름차순 정렬한 뒤 이분 탐색으로 각 원소들을 구해주면 된다.
중요한 점은 a_i와 가장 가까운 B의 원소가 2개일 때 작은 것을 사용해야 한다는 것이다.
이 조건을 놓치고 풀어서 어떤 부분이 잘못 되었는지 찾느라 시간을 낭비했다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N, M; cin >> N >> M;
vector<int> v(N), u(M);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; i<M; i++) cin >> u[i];
sort(u.begin(), u.end());
vector<int> w(N);
for(int i=0; i<N; i++) {
int l = 0, r = M-1, diff = INT_MAX;
while(l <= r) {
int m = (l + r)/2;
if(abs(v[i] - u[m]) < abs(diff)) {
w[i] = u[m];
diff = v[i] - u[m];
}
else if(abs(v[i] - u[m]) == abs(diff) && u[m] < w[i]) {
w[i] = u[m];
}
if(v[i] - u[m] == 0) break;
if(v[i] - u[m] > 0) l = m + 1;
else if(v[i] - u[m] < 0) r = m - 1;
}
}
int sum = 0;
for(int i=0; i<N; i++) sum += w[i];
cout << sum << "\n";
}
}
백준 BOJ 9873번 : Cow Baseball
문제 난이도 : Silver III
알고리즘 분류 : 브루트포스
N마리의 소들이 1차원 좌표 위에 서 있고, 세 소를 뽑았을 때 3번째 소의 위치 - 2번째 소의 위치가 2번째 소의 위치 - 1번째 소의 위치보다 크거나 같고 2배보다 작거나 같을 때 가능한 조합의 수를 구하는 문제이다.
C++은 속도가 빠른 편에 속하고 N = 1000 이하이므로 O(N^3)에도 충분히 돌아간다.
따라서 브루트포스로 구현이 가능하다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end());
int ans = 0;
for(int i=0; i<N; i++)
for(int j=i+1; j<N; j++)
for(int k=j+1; k<N; k++)
if(v[k] - v[j] >= v[j] - v[i]
&& v[k] - v[j] <= (v[j] - v[i]) * 2) ans++;
cout << ans << "\n";
}
백준 BOJ 17266번 : 어두운 굴다리
문제 난이도 : Silver IV
알고리즘 분류 : 이분 탐색
길이 N인 길 위에 M개의 가로등이 있고, 각 가로등이 양쪽으로 일정한 거리까지 빛을 비춘다고 할 때, 모든 길을 빛으로 덮기 위한 최소 가로등 불빛의 거리를 구하는 문제이다.
조건을 만족하는 최솟값을 구하는 문제이기 때문에 이분 탐색으로 풀이할 수 있다.
최소 거리는 1, 최대 거리는 N으로 놓고 이분 탐색을 수행해주면 답을 찾을 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(M);
for(int i=0; i<M; i++) cin >> v[i];
int l = 1, r = N, ans = N;
while(l <= r) {
int m = (l + r)/2;
bool check = true;
if(v[0] - m > 0) check = false;
if(v[M-1] + m < N) check = false;
for(int i=1; i<M; i++)
if(v[i-1] + m < v[i] - m) check = false;
if(check) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
cout << ans << "\n";
}
백준 BOJ 20551번 : Sort 마스터 배지훈의 후계자
문제 난이도 : Silver IV
알고리즘 분류 : 정렬, 이분 탐색
정렬한 배열에서 특정 수가 몇 번째에 나오는지를 찾고, 만약 나오지 않는다면 -1을 출력하는 문제이다.
sort 함수와 upper_bound, lower_bound를 활용할 줄 알면 쉽게 풀 수 있는 문제이다.
만약 벡터 v에 원소 x가 존재하지 않는 경우 upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x) 값이 0이기 때문에 -1을 출력해주면 되고, 그렇지 않은 경우 lower_bound로 최초로 나타나는 주소를 출력해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end());
while(M--) {
int x; cin >> x;
if(upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x) == 0) cout << -1 << "\n";
else cout << lower_bound(v.begin(), v.end(), x) - v.begin() << "\n";
}
}
백준 BOJ 24331번 : ДВА АЛБУМА
문제 난이도 : Silver IV
알고리즘 분류 : 해시를 사용한 집합과 맵
N개의 정수와 M개의 정수가 주어질 때, 두 정수열 모두에 포함된 정수의 개수를 구하고, 그 목록을 오름차순으로 출력하는 문제이다.
해시를 사용한 집합과 맵으로 풀이하였다.
먼저 N개의 수열을 입력받을 때 map에 체크를 해두었다가, 다음 M개의 수열을 입력받으며 체크가 되어있는 수열만 따로 벡터에 저장한 뒤 정렬해주고 그 size와 목록을 출력하도록 구현하였다.
참고로 이 문제는 이분 탐색으로도 풀이할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
map<int, bool> m;
while(N--) {
int x; cin >> x;
m[x] = true;
}
vector<int> v;
while(M--) {
int x; cin >> x;
if(m[x]) v.push_back(x);
}
sort(v.begin(), v.end());
cout << v.size() << "\n";
for(int i=0; i<v.size(); i++) cout << v[i] << " ";
cout << "\n";
}
백준 BOJ 11976번 : Promotion Counting
문제 난이도 : Silver V
알고리즘 분류 : 수학
대회 전과 후의 브론즈, 실버, 골드, 플래티넘 등급의 사람의 수가 주어질 때 각 등급을 승격한 사람의 수를 구하는 문제이다.
간단히 방정식을 세워보면, 플래티넘으로 승급한 사람은 플래티넘 사람의 전후 숫자의 차이로 알 수 있다.
골드로 승급한 사람은 골드를 지나 플래티넘까지 승급한 사람까지 고려해야 하므로 플래티넘 사람의 전후 숫자에 골드 사람의 전후 숫자를 합하여 구할 수 있다.
이런 방식으로 세 등급의 전후 차이로 승급한 사람의 수를 구해줄 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int v[4][2];
for(int i=0; i<4; i++)
for(int j=0; j<2; j++) cin >> v[i][j];
int a = (v[1][1] - v[1][0]) + (v[2][1] - v[2][0]) + (v[3][1] - v[3][0]);
int b = (v[2][1] - v[2][0]) + (v[3][1] - v[3][0]);
int c = (v[3][1] - v[3][0]);
cout << a << "\n" << b << "\n" << c << "\n";
}
백준 BOJ 9443번 : Arrangement of Contest
문제 난이도 : Bronze III
알고리즘 분류 : 문자열
N개의 문자열이 주어질 때, 맨 앞 문자가 A인 문자열, 맨 앞 문자가 B인 문자열, ... 순으로 놓을 때 최대 몇 개의 문자열을 놓을 수 있는지를 구하는 문제이다.
N이 크지 않으므로 모든 알파벳에 대해 N개의 문자열을 모두 검사해보면서 답을 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<string> v(N);
for(int i=0; i<N; i++) cin >> v[i];
int ans = 0;
for(int i=0; i<26; i++) {
bool check = false;
for(int j=0; j<N; j++)
if(v[j][0] == char('A' + i)) check = true;
if(check) ans++;
else break;
}
cout << ans << "\n";
}
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 백준 BOJ 풀이 : 데이크스트라, 이분 탐색, 그래프 등 220724 (0) | 2022.07.24 |
|---|---|
| 백준 BOJ 풀이 : 이분 탐색 문제들 마저 해치우기 (220723) (0) | 2022.07.23 |
| 백준 BOJ 풀이 : 이분 탐색, 조합론(완전순열, 카탈란 수) 문제 등 (220721) (0) | 2022.07.21 |
| 220720 백준 BOJ 풀이 : LIS (가장 긴 증가하는 부분 수열) 문제들 (0) | 2022.07.20 |
| 220719 백준 풀이 : BOJ 18977, BOJ 25369, BOJ 25370 등 (0) | 2022.07.19 |