백준 BOJ 21739번 : 펭귄 네비게이터
문제 난이도 : Gold II
알고리즘 분류 : 조합론, DP
2 x N 격자에서 펭귄이 어떤 경로로 오른쪽과 아래로만 이동하더라도 더 큰 번호로만 이동하며 도착할 수 있도록 번호를 매긴다고 할 때 경우의 수를 구하는 문제이다.
높이가 2이므로 2부터 N-1까지 위쪽 또는 아래쪽 줄을 선택하면서 번호를 매길 수 있다.
규칙을 찾아보면 윗줄보다 아랫줄을 선택하는 순간이 2번 이상일 경우 조건에 어긋나게 된다.
따라서 이는 (0, 0)에서 (N, N)으로 격자를 따라 오른쪽과 아래로만 이동하는데, 아래를 오른쪽보다 2번 이상 선택하지 않는 경우의 수와 같고 이를 시각화하면 다음과 같다.
위는 N = 4일 때의 문제 상황을 앞서 설명한 다른 격자판으로 일대일 대응시킨 것이다.
2(N-1) C (N-1)에서 제외해주어야 하는 경우는 빨간색 선을 넘어가는 경로인데, 예를 들어 위와 같은 파란색 경로를 가지고 빨간색 지점을 넘어가는 최초의 지점을 기준으로 대칭 이동을 시켜보면 위와 같이 원래 목표 지점의 왼쪽 아래로 2칸씩 더 이동한 지점에 도착하게 된다.
이 경로들의 수는 2(N-1) C N-3이므로 최종적으로 답 f(N) = 2(N-1) C (N-1) - 2(N-1) C (N-3)이 된다.
그런데 이 수열은 어디서 많이 본 수열일 것이다.
다음과 같이 규칙성을 찾기 위해 코드를 작성해보았다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[20001][10001] = {};
int mod = (int)(1e9 + 7);
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
for(int i=0; i<=20000; i++) dp[i][0] = 1;
for(int i=1; i<=20000; i++)
for(int j=1; j<=10000; j++) dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod;
for(int i=1; i<=10; i++) {
int N = i;
cout << dp[(N-1)*2][N-1] - dp[(N-1)*2][N-3] << "\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;
int dp[10001] = {1, 1};
for(int i=2; i<=N; i++)
for(int j=0; j<i; j++) dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % (int)(1e9 + 7);
cout << dp[N] << "\n";
}
백준 BOJ 21757번 : 나누기
문제 난이도 : Gold III
알고리즘 분류 : 누적 합, DP
수열을 4개의 부분 수열로 나누어 각 부분 수열의 합이 같도록 하는 경우의 수를 구하는 문제이다.
먼저 수열 전체의 합을 구한다.
만약 수열의 합이 4의 배수가 아니라면 수열은 4등분이 불가능하므로 0을 출력하고 종료해준다.
나머지 경우 중에서는 수열의 합이 0인 경우와 그렇지 않은 경우로 나눠야 한다.
0인 경우는 dp로 해결이 불가능하기 때문이다.
합이 0인 경우는, 부분 누적 합을 구해 1 ~ (N-1)번째 누적 합 중 0의 개수를 세 준 다음 (어차피 N번까지의 누적합은 무조건 0이고 마지막 부분 수열이 끝나는 부분은 무조건 N번째로, 선택의 여지가 없기 때문에 고려할 필요가 없음) 그 중 3개의 위치를 뽑으면 각 부분 수열이 끝나는 위치라고 생각해줄 수 있으므로, 그 중 3개를 뽑으면 된다.
즉, prefix sum 배열을 만들어 1 ~ N-1 중에서 0의 개수를 세고 그 개수가 K라고 하였을 때 K C 3을 답으로 얻을 수 있다.
합이 4의 배수인 경우는, dp를 이용하여 해결할 수 있다.
1번까지의 누적 합부터 뒤로 가면서 검사하면서, (전체 합)/4의 배수에 해당하는 값이 나올 때마다 이전 항의 dp 값만큼을 더해주어 dp 값을 갱신해주면 된다.
예를 들어 수열의 전체 합이 4인데, 누적 합이 1인 것이 2번 나왔고 이번에 2가 나왔다면 앞에 1이 2번 나왔으므로 앞의 1과 지금 2를 선택해서 1과 2를 만들 수도 있고, 뒤의 1과 지금의 2를 선택해서 1과 2를 만들 수 있기 때문에 dp[2]에는 2가 더해져야 하는 것이다.
이런 식으로 더해서 dp[3]을 답으로 구해주면 된다.
dp[4]는 의미가 없는 것이 어차피 4번째 부분 수열은 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<int> v(N+1);
for(int i=1; i<=N; i++) cin >> v[i];
vector<int> u(N+1);
for(int i=1; i<=N; i++) u[i] = u[i-1] + v[i];
if(u[N] % 4 != 0) {
cout << 0 << "\n";
return 0;
}
if(u[N] == 0) {
int cnt = 0;
for(int i=1; i<N; i++)
if(u[i] == 0) cnt++;
cout << cnt * (cnt - 1) * (cnt - 2) / 6 << "\n";
return 0;
}
int unit = u[N] / 4;
vector<int> dp(5);
for(int i=1; i<=N; i++) {
if(u[i] % unit != 0) continue;
if(u[i] / unit <= 0) continue;
if(u[i] / unit == 1) dp[1]++;
else dp[u[i] / unit] += dp[u[i] / unit - 1];
}
cout << dp[3] << "\n";
}
백준 BOJ 17268번 : 미팅의 저주
문제 난이도 : Gold III
알고리즘 분류 : 조합론, DP
원 위에 짝수 N개의 점이 있을 때, 각 점은 하나의 선분의 끝이 되고 선분이 서로 교차하지 않도록 N/2개의 선분을 긋는 경우의 수를 구하는 문제이다.
N = 2부터 N = 8까지만 해보면 이 수가 카탈란 수열임을 알 수 있다.
간단히 증명을 해보자면, 하나의 점을 기준으로 어떤 점으로 잇는지에 따라 케이스를 나눠볼 수 있다.
이를 이용하면 하나의 점을 기준으로 가장 왼쪽에 잇는 경우는 f(N-2) 가지가 되고, 그 다음 점에 잇는 것은 존재하는 경우의 수가 없으므로 넘어가고, 그 다음 점에 이으면 나올 수 있는 경우의 수는 f(2) * f(N-4)가 되고, ... 이런 식으로 되므로 이에 대한 식을 써보면 점화식이 카탈란 수에 대한 점화식임을 알 수 있다.
따라서 문제의 답이 카탈란 수열의 N/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 N; cin >> N;
N /= 2;
int dp[5001] = {1, 1};
for(int i=2; i<=N; i++)
for(int j=0; j<i; j++) dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % 987654321;
cout << dp[N] << "\n";
}
백준 BOJ 18132번 : 내 이진트리를 돌려줘!!!
문제 난이도 : Gold III
알고리즘 분류 : DP
간선의 수를 N이라고 할 때, 간선 N개로 만들 수 있는 이진 트리의 수를 구하는 문제이다.
이 문제 역시 N = 1 ~ 4 정도만 해봐도 카탈란 수열이 나타남을 알 수 있다.
#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;
N++;
int dp[5001] = {1, 1};
for(int i=2; i<=N; i++)
for(int j=0; j<i; j++) dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % (int)(1e9 + 7);
cout << dp[N] << "\n";
}
백준 BOJ 2143번 : 두 배열의 합
문제 난이도 : Gold III
알고리즘 분류 : 누적 합, 이분 탐색
크기 N인 수열 A와 크기 M인 수열 B가 있을 때 두 부분 배열의 합이 K인 조합의 수를 구하는 문제이다.
N과 M이 1000 이하이므로, 누적 합을 이용하여 N^2 정도의 부분합을 모두 구해서 각 벡터에 넣어주고, 이분 탐색으로 가능한 조합을 모두 찾아줘도 시간 초과에 걸리지 않는다.
시간 복잡도는 N과 M을 구분하지 않고 나타내면 대략 (O(N^2 log(N^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 K; cin >> K;
int N; cin >> N;
vector<int> v(N+1);
for(int i=1; i<=N; i++) {
int x; cin >> x;
v[i] = v[i-1] + x;
}
int M; cin >> M;
vector<int> u(M+1);
for(int i=1; i<=M; i++) {
int x; cin >> x;
u[i] = u[i-1] + x;
}
vector<int> vsum;
for(int i=1; i<=N; i++)
for(int j=0; j<i; j++) vsum.push_back(v[i] - v[j]);
vector<int> usum;
for(int i=1; i<=M; i++)
for(int j=0; j<i; j++) usum.push_back(u[i] - u[j]);
sort(vsum.begin(), vsum.end());
sort(usum.begin(), usum.end());
int ans = 0;
for(int i=0; i<vsum.size(); i++)
ans += upper_bound(usum.begin(), usum.end(), K - vsum[i])
- lower_bound(usum.begin(), usum.end(), K - vsum[i]);
cout << ans << "\n";
}
백준 BOJ 22236번 : 가희와 비행기
문제 난이도 : Gold IV
알고리즘 분류 : 조합론, DP
비행기가 1만큼의 거리당 1만큼 상승 또는 하강하여 1 이상의 고도를 유지한 뒤 N만큼의 거리를 비행하는 방법의 수를 구하는 문제이다.
1 이상의 위치에서는 상승이 하강보다 같거나 많은 상태를 유지하면 되므로 이것은 카탈란 수와 대응시켜서 생각해볼 수 있다.
다만 0 이상이 아닌 1 이상의 고도를 유지해야 하므로 처음 0 → 1로 가는 한 칸과 1 → 0으로 가는 마지막 한 칸을 제외하고 생각하면 된다.
즉, M = (N-2)/2에 대해 카탈란 수의 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;
N = (N - 2)/2;
vector<int> dp(max(N+1, (int)2));
dp[0] = 1, dp[1] = 1;
for(int i=2; i<=N; i++)
for(int j=0; j<i; j++) dp[i] = (dp[i] + dp[j]*dp[i-1-j]) % M;
cout << dp[N] << "\n";
}
백준 BOJ 17197번 : Fence Planning
문제 난이도 : Silver I
알고리즘 분류 : 분리 집합(인줄 알았으나 DFS로도 풀린다고 한다.)
각 소의 2차원 좌표가 주어지고 연결 관계인 소들의 그룹 중 가장 직사각형 둘레를 작게 펜스를 칠 수 있는 그룹의 펜스 둘레를 구하는 문제이다.
나의 경우에는 disjoint set으로 같은 그룹인 것들을 묶어주고 그들 중 최대, 최소 x y 좌표를 계승해주는 방식으로 문제를 어렵게 풀었는데, 생각해보니 DFS로 하면 훨씬 간단하게 풀릴 것 같다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int sx, sy, lx, ly; };
vector<s> v;
vector<int> u;
int f(int x) {
if(u[x] == x) return x;
else return u[x] = f(u[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
v.resize(N+1);
for(int i=1; i<=N; i++) {
cin >> v[i].sx >> v[i].sy;
v[i].lx = v[i].sx;
v[i].ly = v[i].sy;
}
u.resize(N+1);
for(int i=1; i<=N; i++) u[i] = i;
while(M--) {
int a, b; cin >> a >> b;
if(f(a) != f(b)) {
v[f(b)].sx = min(v[f(b)].sx, v[f(a)].sx);
v[f(b)].sy = min(v[f(b)].sy, v[f(a)].sy);
v[f(b)].lx = max(v[f(b)].lx, v[f(a)].lx);
v[f(b)].ly = max(v[f(b)].ly, v[f(a)].ly);
u[f(a)] = f(b);
}
}
int ans = INT_MAX;
for(int i=1; i<=N; i++)
ans = min(ans, ((v[f(i)].lx - v[f(i)].sx) + (v[f(i)].ly - v[f(i)].sy)) * 2);
cout << ans << "\n";
}
백준 BOJ 7511번 : 소셜 네트워킹 어플리케이션
문제 난이도 : Gold V
알고리즘 분류 : 분리 집합, 그래프 탐색
주어진 그래프와 노드 쌍들에 대해 노드 쌍들이 연결 관계인지 여부를 구하는 문제이다.
간단한 분리 집합 문제로, 분리 집합에 대한 개념만 있으면 풀이 가능하다.
각 테스트케이스마다 parent 배열을 초기화해주는 것을 잊지 말자.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
int f(int x) {
if(x == v[x]) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
for(int t=1; t<=T; t++) {
cout << "Scenario " << t << ":\n";
int N; cin >> N;
v.resize(N);
for(int i=0; i<N; i++) v[i] = i;
int M; cin >> M;
while(M--) {
int a, b; cin >> a >> b;
if(f(a) != f(b)) v[f(a)] = f(b);
}
int K; cin >> K;
while(K--) {
int a, b; cin >> a >> b;
if(f(a) == f(b)) cout << 1 << "\n";
else cout << 0 << "\n";
}
cout << "\n";
}
}
백준 BOJ 16397번 : 탈출
문제 난이도 : Gold IV
알고리즘 분류 : BFS
주어진 수에서 시작하여 1을 더하거나, 2배를 하여 맨 앞자리 수를 1 감소시키는 연산을 하여 특정한 수를 만든다고 할 때, 특정 횟수 이하로 변환이 가능하다면 그 횟수를 출력하고 그렇지 않다면 ANG을 출력하는 문제이다.
1 ~ 99999 범위 내에서 연산이 수행되는 것이므로 BFS로 충분히 수행이 가능하다.
다만 맨 앞자리 수를 1 감소시키는 부분을 구현하는 데에서 약간의 고착이 있었는데, str[0]--과 같은 코드가 작동하지 않아 그냥 pow(10, str.length()-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, K; cin >> N >> M >> K;
queue<int> q;
q.push(N);
vector<int> vis(100000, -1);
vis[N] = 0;
while(!q.empty()) {
int x = q.front();
q.pop();
if(x == K) {
if(vis[K] <= M) cout << vis[K] << "\n";
else cout << "ANG\n";
return 0;
}
if(x+1 < 100000 && vis[x+1] == -1) {
vis[x+1] = vis[x] + 1;
q.push(x+1);
}
if(x*2 >= 100000) continue;
string str = to_string(x*2);
int y = x*2 - pow(10, str.length()-1);
if(y < 100000 && vis[y] == -1) {
vis[y] = vis[x] + 1;
q.push(y);
}
}
cout << "ANG\n";
}
백준 BOJ 16463번 : 13일의 금요일
문제 난이도 : Silver III
알고리즘 분류 : 브루트포스
2019년 1월 1일부터 N년까지 나타나는 13일의 금요일의 수를 세는 문제이다.
문제에서는 2019년 1월 1일이 화요일이라는 힌트를 제시해준다.
2019년 1월 1일부터 날짜의 수를 누적시키면서 그것을 7로 나눈 나머지가 특정한 값인지를 확인하면서 세주면 될 것이다.
7로 나눈 나머지가 0인 것을 월요일, 1을 화요일, ...과 같이 둔다고 하자.
그럼 2019년 1월 1일이 화요일이므로 0으로 두고 계산을 시작하면 된다.
왜냐하면 sum에 1을 더한 1이 2019년 1월 1일을 의미하고 이것의 나머지는 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; cin >> N;
int v[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int sum = 0, ans = 0;
for(int i=2019; i<=N; i++) {
if((i % 4 == 0 && i % 100 != 0) || i % 400 == 0) v[1] = 29;
else v[1] = 28;
for(int j=0; j<12; j++) {
if((sum + 13) % 7 == 4) ans++;
sum += v[j];
}
}
cout << ans << "\n";
}
백준 BOJ 20920번 : 영단어 암기는 괴로워
문제 난이도 : Silver III
알고리즘 분류 : 정렬, 해시를 사용한 집합과 맵
영단어들이 주어질 때, 조건에 따라 중복되지 않도록 단어 리스트를 출력하는 문제이다.
먼저 영단어가 중복되어 나올 수도 있으므로 map을 반드시 사용해주어야 한다.
그 다음, 정렬 bool 함수를 따로 정의해주어야 한다.
벡터를 따로 선언하여 중복되지 않도록 map으로 체크한 뒤에 push_back 해주고, 정의한 비교 함수로 정렬해주면 된다.
bool cmp 함수에서 else 다음에 return을 반드시 써주도록 주의하자. (실수하기가 쉽다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
map<string, int> m;
bool cmp(string a, string b) {
if(m[a] != m[b]) return m[a] > m[b];
else if(a.length() != b.length()) return a.length() > b.length();
else return a < b;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<string> v;
while(N--) {
string str; cin >> str;
if(str.length() < M) continue;
if(m[str] == 0) v.push_back(str);
m[str]++;
}
sort(v.begin(), v.end(), cmp);
for(int i=0; i<v.size(); i++) cout << v[i] << "\n";
}
백준 BOJ 14569번 : 시간표 짜기
문제 난이도 : Silver II
알고리즘 분류 : 구현
수업들의 시간표와 학생들의 시간표가 주어질 때 각 학생이 들을 수 있는 수업들의 개수를 구하는 문제이다.
문제 분류 자체는 비트마스킹으로 되어있었는데, 변수들의 범위가 50까지밖에 안돼서 O(N^4)과 같은 시간 복잡도에도 무난히 통과되는 문제이다.
즉, 벡터를 사용하여 브루트포스로 일일이 시간을 체크해보면서 구현해주면 된다.
#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<vector<int>> v(N);
for(int i=0; i<N; i++) {
int x; cin >> x;
for(int j=0; j<x; j++) {
int y; cin >> y;
v[i].push_back(y);
}
}
int M; cin >> M;
while(M--) {
int x; cin >> x;
vector<int> u(x);
for(int i=0; i<x; i++) cin >> u[i];
int ans = 0;
for(int i=0; i<N; i++) {
bool check = true;
for(int j=0; j<v[i].size(); j++) {
bool check2 = false;
for(int k=0; k<u.size(); k++)
if(v[i][j] == u[k]) check2 = true;
if(!check2) check = false;
}
if(check) ans++;
}
cout << ans << "\n";
}
}
백준 BOJ 15828번 : Router
문제 난이도 : Silver IV
알고리즘 분류 : 큐
크기가 N인 버퍼에 0이 입력되면 버퍼에 가장 먼저 들어왔던 자료 중 하나를 비우고 다른 값이 들어오면 해당 값을 버퍼의 맨 뒤에 넣는 과정을 반복하여 마지막에 들어있는 자료들을 구하는 문제이다.
간단히 읽어봐도 큐의 자료구조 형식을 가지고 있음을 알 수 있다.
큐를 이용하여 구현해주면 되고, 큐에 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;
queue<int> q;
while(true) {
int x; cin >> x;
if(x == -1) break;
if(x == 0) {
q.pop();
continue;
}
if(q.size() >= N) continue;
q.push(x);
}
if(q.empty()) {
cout << "empty\n";
return 0;
}
while(!q.empty()) {
cout << q.front() << " ";
q.pop();
}
cout << "\n";
}
백준 BOJ 12001번 : Load Balancing (Bronze)
문제 난이도 : Silver V
알고리즘 분류 : 브루트포스
소를 4개의 구간으로 분할하여 그 중 가장 소가 많은 그룹의 소의 수가 최소가 되도록 하는 문제이다.
원래는 브루트포스 알고리즘으로 나눌 수 있는 경우를 모두 나누어 보면서 최솟값을 찾으면 되는데, 나의 경우에는 이 문제의 Silver 버전을 이미 풀었었기 때문에 입력부만 조금 수정하여 제출했다.
#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<pair<int, int>> vx(N+1), vy(N+1);
for(int i=1; i<=N; i++) {
cin >> vx[i].first >> vy[i].first;
vx[i].second = vy[i].second = i;
}
sort(vx.begin()+1, vx.end());
sort(vy.begin()+1, vy.end());
struct p { int x, y; };
vector<p> v(N+1);
int xcnt = 1, ycnt = 1;
for(int i=1; i<=N; i++) {
if(i > 1 && vx[i].first > vx[i-1].first) xcnt++;
v[vx[i].second].x = xcnt;
}
for(int i=1; i<=N; i++) {
if(i > 1 && vy[i].first > vy[i-1].first) ycnt++;
v[vy[i].second].y = ycnt;
}
vector<vector<int>> u(xcnt+1, vector<int>(ycnt+1));
for(int i=1; i<=N; i++) u[v[i].x][v[i].y]++;
vector<vector<int>> w(xcnt+1, vector<int>(ycnt+1));
for(int i=1; i<=xcnt; i++)
for(int j=1; j<=ycnt; j++)
w[i][j] = w[i-1][j] + w[i][j-1] - w[i-1][j-1] + u[i][j];
int ans = INT_MAX;
for(int i=1; i<=xcnt; i++)
for(int j=1; j<=ycnt; j++) {
int x = max({w[i][j],
w[i][ycnt] - w[i][j],
w[xcnt][j] - w[i][j],
w[xcnt][ycnt] - w[i][ycnt] - w[xcnt][j] + w[i][j]});
ans = min(ans, x);
}
cout << ans << "\n";
}
백준 BOJ 5545번 : 최고의 피자
문제 난이도 : Silver III
알고리즘 분류 : 그리디, 정렬
피자의 도우와 토핑 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;
int a, b; cin >> a >> b;
int x; cin >> x;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end(), greater<int>());
int ans = x / a;
int sum = 0;
for(int i=0; i<N; i++) {
sum += v[i];
ans = max(ans, (x + sum)/(a + b*(i+1)));
}
cout << ans << "\n";
}
백준 BOJ 4396번 : 지뢰 찾기
문제 난이도 : Silver V
알고리즘 분류 : 구현
지뢰 찾기를 구현하는 문제이다.
지뢰를 누른 경우의 구현이 까다로운데, 예제에 제대로 나와있지 않아 문제를 자세히 읽어보거나 어떻게 출력해야 하는지를 여러 번 시도해보는 수밖에 없다.
문제에서 요구한 조건은, 지뢰를 눌렀어도 나머지 누른 칸에 대해서는 숫자가 나타나야 하며 거기에 추가로 지뢰가 있는 칸을 모두 *(asterisk)로 출력하라는 의미이다.
#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<vector<char>> v(N, vector<char>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) cin >> v[i][j];
vector<vector<char>> u(N, vector<char>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) cin >> u[i][j];
bool check = true;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
if(v[i][j] == '*' && u[i][j] == 'x') check = false;
int di[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dj[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(!check && v[i][j] == '*') {
cout << "*";
continue;
}
if(u[i][j] == '.') {
cout << ".";
continue;
}
int cnt = 0;
for(int k=0; k<8; k++) {
int ni = i + di[k];
int nj = j + dj[k];
if(ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
if(v[ni][nj] == '*') cnt++;
}
cout << cnt;
}
cout << "\n";
}
}
백준 BOJ 14405번 : 피카츄
문제 난이도 : Silver V
알고리즘 분류 : 문자열
문자열이 pi, ka, chu 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);
string str; cin >> str;
bool check = true;
for(int i=0; i<str.length(); i++) {
if(str[i] == 'p' && i+1 < str.length() && str[i+1] == 'i') i++;
else if(str[i] == 'k' && i+1 < str.length() && str[i+1] == 'a') i++;
else if(str[i] == 'c' && i+2 < str.length() && str[i+1] == 'h' && str[i+2] == 'u') i += 2;
else check = false;
}
if(check) cout << "YES\n";
else cout << "NO\n";
}
백준 BOJ 1235번 : 학생 번호
문제 난이도 : Silver IV
알고리즘 분류 : 문자열
뒤에서 k자리만큼 자른 문자열들이 모두 다르게 하는 k의 최솟값을 구하는 문제이다.
substr 함수를 사용할 줄 안다면 브루트포스로 쉽게 구현이 가능하다.
직접 뒤에서부터 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; cin >> N;
vector<string> v(N);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; i<v[0].length(); i++) {
vector<string> u(N);
for(int j=0; j<N; j++)
u[j] = v[j].substr(v[j].length()-1-i, i+1);
sort(u.begin(), u.end());
bool check = true;
for(int i=1; i<N; i++)
if(u[i] == u[i-1]) check = false;
if(check) {
cout << i+1 << "\n";
break;
}
}
}
백준 BOJ 3005번 : 크로스워드 퍼즐 쳐다보기
문제 난이도 : Silver II
알고리즘 분류 : 문자열
크로스워드 퍼즐 형식의 문자 배열이 주어질 때, 가로 또는 세로로 스캔하면서 읽을 수 있는 2자리 이상의 문자열들 중 사전순으로 가장 앞서는 문자열을 출력하는 문제이다.
가로 또는 세로로 배열을 스캔하면서 단어를 완성해주고, 조건대로 문자열의 길이가 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 N, M; cin >> N >> M;
vector<vector<char>> v(N, vector<char>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) cin >> v[i][j];
vector<string> u;
string str = "";
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) {
if(v[i][j] >= 'a' && v[i][j] <= 'z') str += v[i][j];
if(v[i][j] == '#' || j == M-1) {
if(str.length() >= 2) u.push_back(str);
str = "";
}
}
for(int j=0; j<M; j++)
for(int i=0; i<N; i++) {
if(v[i][j] >= 'a' && v[i][j] <= 'z') str += v[i][j];
if(v[i][j] == '#' || i == N-1) {
if(str.length() >= 2) u.push_back(str);
str = "";
}
}
sort(u.begin(), u.end());
cout << u[0] << "\n";
}
백준 BOJ 20186번 : 수 고르기
문제 난이도 : Silver III
알고리즘 분류 : 정렬
N개의 수 중에서 M개의 수를 고를 때, 각 수는 자신의 왼쪽에 골라진 수의 개수만큼 자신의 수에서 뺀 값들의 합이 최대가 되도록 하는 값을 구하는 문제이다.
생각해보면 M개의 수를 고를 때 빼지는 수는 M * (M-1) / 2로 고정이다.
따라서 가장 큰 M개의 수를 고르고 그 합에서 M * (M-1) / 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 N, M; cin >> N >> M;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end(), greater<int>());
int ans = 0;
for(int i=0; i<M; i++) ans += v[i];
ans -= M * (M-1) / 2;
cout << ans << "\n";
}
백준 BOJ 16165번 : 걸그룹 마스터 준석이
문제 난이도 : Silver III
알고리즘 분류 : 해시를 사용한 집합과 맵
걸그룹의 이름과 멤버 이름들이 주어질 때, M개의 퀴즈에 대해 걸그룹의 이름이 들어오면 멤버의 이름을 출력하고, 멤버의 이름이 입력으로 들어오면 걸그룹의 이름을 출력하는 문제이다.
map을 사용해 풀이해주면 되는데, map은 단순히 string에서 string으로만 연결할 수 있는 것이 아니라 string에서 vector, 또는 vector에서 string으로도 연결이 가능하므로 이를 유용하게 사용하여 문제를 풀이할 수 있다.
#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<string, string> m;
map<string, vector<string>> m2;
while(N--) {
string a; cin >> a;
int K; cin >> K;
while(K--) {
string b; cin >> b;
m[b] = a;
m2[a].push_back(b);
}
sort(m2[a].begin(), m2[a].end());
}
while(M--) {
string str; cin >> str;
int x; cin >> x;
if(x == 0) {
for(int i=0; i<m2[str].size(); i++) cout << m2[str][i] << "\n";
}
else if(x == 1) {
cout << m[str] << "\n";
}
}
}
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 220718 백준 BOJ 풀이 : 그래프 탐색 문제들 (너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)) (4) | 2022.07.18 |
|---|---|
| 220717 백준 BOJ 풀이 : 2차원 배열 탐색, 정렬 문제 등 풀이 (0) | 2022.07.17 |
| 220715 PS 일기 : 탐색(DFS, BFS, 백트래킹), 그리디 쉬운 문제들 (실버 ~ 골드) (0) | 2022.07.15 |
| 220714 PS 일기 : DP 알고리즘, 포함-배제 원리, 분리 집합(union find) 등 (0) | 2022.07.14 |
| 220713 PS 일기 : 각종 DP 문제들 풀이 (O(N^2) 실버~골드 난이도) (0) | 2022.07.13 |