문제 + 풀이
[문제 후기]
A. Trident (9분)
문제 링크
간단하게 문제의 조건에 따라 삼지창을 그리면 된다.
for문을 이용하면 쉽게 그릴수 있는 문제다.
구현
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t,s,h;
cin >> t>>s>>h;
int tmp = s;
string str = "";
string str2 = "";
string tmpSt = "";
for (int i = 0; i < tmp; i++) {
tmpSt += ' ';
}
str = '*' + tmpSt + '*' + tmpSt + '*';
for (int i = 0; i < t; i++) {
cout << str << "\n";
}
for (int i = 0; i < s; i++) {
str2 += '*';
}
cout << "*"<<str2<<"*"<<str2<<"*\n";
for (int i = 0; i < h; i++) {
cout << ' ' << tmpSt << "*\n";
}
return 0;
}
B. 다각형 (9분)
문제 링크
이 문제는 잘 생각하면 n각형에서 n이 짝수일 경우만 하나의 선분으로 n각형의 변을 자를 수 있다.
그러므로 a~b 사이에 짝수인 변들의 합을 계산하면 되는 문제다.
구현
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int a, b;
cin >> a >> b;
long long stA = ((a + 1) / 2) * 2;
long long edB = (b / 2) * 2;
if (stA <= 2) {
stA = 4;
}
if (edB < stA) {
cout << 0;
}
else {
long long num = ((edB - stA) / 2)+1;
cout << num * (stA + edB) / 2;
}
return 0;
}
C. Cakey McCakeFace (30분)
문제 링크
이번 마라톤에서 가장 오래 걸린 문제다. 귀찮아서 번역해서 문제를 읽었더니 문제의 내용이 도저히 이해가 안돼서 한참을 고민했었다. 중간에 다시 여러 번 문제를 읽은 후에야 이해가 됐다.
문제의 내용을 쉽게 요약하면 빵을 굽는시간 t가 걸리는데 제대로 측정이 되지 않을 수 있다.
그러므로 빵을 굽는 시간 t를 특정 시간으로 가정했을 경우 제대로 측정된 경우가 가장 많은 경우를 찾고 그 때의 시간 t를 찾으면 되는 문제다.
이 문제는 시간이 겹치지 않으므로 모든 입력에 대해 빠져나오는 시간과 차이를 구하고, 그 중에서 가장 시간 차이가 같은 값이 많은 시간을 찾으면 되는 문제다.
구현
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <set>
#include <map>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int N, M;
cin >> N >> M;
vector<int> vN(N);
vector<int> vM(M);
unordered_map<int, int> mm;
for (int i = 0; i < N; i++) {
cin >> vN[i];
}
for (int i = 0; i < M; i++) {
cin >> vM[i];
}
set<int> numSet;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (vM[j] - vN[i] >= 0) {
mm[vM[j] - vN[i]] += 1;
}
}
}
vector<pair<int, int>> V(mm.begin(), mm.end());
sort(V.begin(), V.end(), [](pair<int,int>a, pair<int,int>b) {
return a.second == b.second ? a.first<b.first : a.second>b.second;
});
if (V.size() > 0) {
cout << V[0].first;
}
else {
cout << 0;
}
return 0;
}
D. 주식 (10분)
문제 링크
이 문제는 주식의 판매이익을 최대로 올리면 되는 문제다.
잘 생각하면 현재 주식가격보다 높은 주식이 없다면 주식을 안 사면 된다는 결론이 나온다.
그러므로 거꾸로 뒤에서부터 탐색을 시작해 주식의 최대가격을 저장해 나간다.
이후 이전에 등장했던 최대가격보다 더 높은 최대가격이 앞에 있다면, 앞에 등장하는 주식들은 갱신된 주식의 최대 가격으로 판매하면 된다.
구현
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <set>
#include <map>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int tc;
cin >> tc;
for (int t = 0; t < tc; t++) {
int N;
cin >> N;
vector<int> v(N);
for (int i = 0; i < N; i++) {
cin >> v[i];
}
long long maxCost = v[N - 1];
int cnt = 0;
long long hap = 0;
long long maxAns = 0;
long long tmp;
for (int i = N - 2; i >= 0; i--)
{
if (v[i] < maxCost) {
cnt += 1;
hap += v[i];
}
else
{
tmp = cnt * maxCost - hap;
if (tmp > 0) {
maxAns += tmp;
}
cnt = 0;
hap = 0;
maxCost = v[i];
}
}
tmp = cnt * maxCost - hap;
if (tmp > 0) {
maxAns += tmp;
}
cout << maxAns << "\n";
}
return 0;
}
E. 소셜 광고 (18분)
문제 링크
이 문제는 나와 직접 연결된 친구만 광고가 같이 보여지기 때문에 완전 탐색을 해야한다.
최근에 비트마스킹을 익혔기 때문에 DFS 대신 비트마스킹으로 광고를 볼 친구들을 선택해 문제를 해결했다.
비트마스킹에서 광고를 받을 사람이 정해지면 그 사람과 친구들에게 광고를 보여준 후 모든 사람이 광고를 볼 수 있는지 체크하면 해결할 수 있는 문제였다.
구현
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <set>
#include <map>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int tc;
cin >> tc;
for (int t = 0; t < tc; t++) {
int N;
cin >> N;
vector<int> V(N,0);
int M, num;
for (int i = 0; i < N; i++) {
cin >> M;
V[i] = 1 << i;
for (int j = 0; j < M; j++) {
cin >> num;
V[i]|=1<<(num - 1);
}
}
int idx, visited;
int minV = N;
for (int i = 1; i < (1 << N) - 1; i++) {
visited = 0;
for (int j = 0; j < N; j++) {
idx = 1 << j;
if ((i & idx) != 0)
{
visited |= V[j];
}
}
if (visited == (1 << N) - 1)
{
int cnt = 0;
for (int j = 0; j < N; j++)
{
idx = 1 << j;
if ((i & idx) != 0)
{
cnt++;
}
}
minV = min(cnt, minV);
}
}
cout << minV << "\n";
}
return 0;
}
F. Cow Picnic (17분)
문제 링크
이 문제는 소들이 한 위치에서 모일 수 있는지 파악한 후 총 몇 개의 위치에서 모든 소들이 모일 수 있는지 출력하면 되는 문제다.
여기서 단방향 그래프이기 때문에 소들의 처음 위치에 따라서 방문할 수 있는 위치가 다르다.
그러므로 소들의 시작 위치를 고려해 어느 위치에 방문할 수 있는지 파악을 한 다음 모든 소들이 방문할 수 있는 지점을 계산하면 쉽게 풀 수 있는 문제다.
구현
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <set>
#include <map>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int K, N, M;
cin >> K >> N >> M;
//k는 소 수, N은 목초지 수, M은 경로 수
vector<int> cows(K);
for (int i = 0; i < K; i++) {
cin >> cows[i];
}
vector<vector<int>>graph(N+1);
vector<vector<bool>>visited(N + 1, vector<bool>(N + 1,false));
int st, ed;
for (int i=0; i<M; i++)
{
cin >> st >> ed;
graph[st].push_back(ed);
}
for (int i = 0; i < K; i++) {
queue<int> q;
visited[cows[i]][cows[i]] = true;
q.push(cows[i]);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int j = 0; j < graph[node].size(); j++) {
if (!visited[cows[i]][graph[node][j]])
{
visited[cows[i]][graph[node][j]] = true;
q.push(graph[node][j]);
}
}
}
}
int Ans = 0;
for (int i = 1; i <= N; i++)
{
bool flag = true;
for (int j = 0; j < K; j++) {
if (!visited[cows[j]][i]) {
flag = false;
break;
}
}
if (flag) {
Ans += 1;
}
}
cout << Ans;
return 0;
}
G. 용액 (10분)
문제 링크
전형적인 투 포인터 문제다.
특성값이 0에 가장 가까운 용액을 만들기 위해 2개의 용액을 섞으므로 가장 특성값이 낮은 용액과 가장 높은 용액을 섞은 후 점차 용액을 바꿔나가면 된다.
오름차순으로 정렬이 된 상태므로 두 용액의 합이 0보다 크면 특성값이 큰 오른쪽 용액을 줄인다.
그러면 두 용액의 특성값이 줄어든다.
반대로 두 용액의 합이 0봐 작다면 특성값이 작은 왼쪽 용액을 오른쪽으로 옮긴다. 그러면 두 용액의 특성값이 늘어난다.
이러한 방법으로 탐색을 하면 고려하지 않아도 되는 경우를 고려하지 않아 O(N)으로 문제를 해결할 수 있다.
구현
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <set>
#include <map>
using namespace std;
const int INF = 2087654321;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int N;
cin >> N;
vector<int> V(N);
for (int i = 0; i < N; i++) {
cin >> V[i];
}
int st = 0, ed=N-1;
int minV=INF;
int stV, edV, tmp;
while(st<ed)
{
if (V[st] + V[ed] < 0) {
tmp = abs(V[st] + V[ed]);
if (minV > tmp) {
minV = tmp;
stV = V[st], edV = V[ed];
}
st++;
}
else if (V[st] + V[ed] > 0)
{
tmp = V[st] + V[ed];
if (minV > tmp) {
minV = tmp;
stV = V[st], edV = V[ed];
}
ed--;
}
else {
cout << V[st] << " " << V[ed];
return 0;
}
}
cout << stV << " " << edV;
return 0;
}
H. 나의 행렬곱셈 답사기 (8분)
문제 링크
이번에 푼 문제 중에 가장 간단하게 구현한 문제다.
행렬의 곱셈 수를 최적으로 곱셈한 방법과 최악으로 곱셈한 방법의 차이가 K가 되는 행렬을 찾으면 되는 문제다.
당연하게도 많은 경우가 있지만, 최대한 단순하게 표현하는게 K를 쉽게 찾을 수 있다.
그래서 행렬 3개를 이용해 K를 만들도록 했다.
행렬 A, B, C가 (a x b), (b x c), (c x d) 로 행렬이 구성됐다고 가정하자.
그러면 이 경우 행렬 곱셈 방법은 아래와 같이 두가지 밖에 없다.
1. AB를 먼저 계산 : (a x b x c) + (a x c x d)
2. BC를 먼저 계산 : (b x c x d) + (a x b x d)
여기서 계산을 단순하게 하기 위해서 b, c, d의 크기를 1로 하면 쉽게 문제를 해결할 수 있다.
그러면 1번과 2번의 계산값은 아래와 같이 단순하게 표현이 된다.
1. a + a
2. 1 + a
위 값을 통해 행렬 곱의 최악과 최선의 차이가 a-1 이므로 k = a-1이다.
그러므로 3개의 행렬이 k+1, 1, 1, 1 이면 행렬곱의 차이가 k가 되는 행렬을 찾을 수 있다.
구현
#include<iostream>
int main()
{
int k;
std::cin>>k;
std::cout<<"3\n"<<k+1<<" 1 1 1";
return 0;
}
[풀이 후기]
마지막 문제가 너무 쉬웠던 것 같다.
이번에는 111분으로 2시간 내에 모든 문제를 해결할 수 있었다.
풀 때 마다 영어 문제가 특히 오래걸리는데 다음번엔 영어 문제가 안나왔으면 좋겠다... ㅠㅠ
'Algorithm > BAEKJOON' 카테고리의 다른 글
| [백준/C++] 색상환 (No. 2482) (0) | 2024.07.03 |
|---|---|
| [백준/C++] RGB거리 2 (No. 17404) (1) | 2024.07.01 |
| [백준/C++] 박성원 (No. 1086) (0) | 2024.06.27 |
| [백준/C++] 외판원 순회 (No. 2098) (0) | 2024.06.24 |
| [백준/C++] 집합 (No. 11723) (0) | 2024.06.23 |