주어진 수가 10보다 작으면, 앞에 0을 붙여서 두 자리로 만들고 각 자리의 숫자 합을 구합니다.
주어진 수의 가장 오른쪽 수와 숫자 합의 가장 오른쪽 수를 붙였을 때 주어진 수가 나올 수 있는 사이클 횟수를 구하는 문제입니다.
주어진 수 : 26
26 => 2 + 6 = 8 (숫자의 합)
68 => 6 + 8 = 14
84 => 8 + 4 = 12
42 => 4 + 2 = 6
26 (4번의 사이클 만에 주어진 수가 나오게 됩니다.)
가장 오른쪽 수를 구할 수 있는 방법은 10을 모듈러 연산하면 쉽게 구할 수 있습니다.
소스 코드
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int temp = n;
int a = 0;
int b = 0;
int sum = 0;
int cycle = 0;
while (true)
{
cycle++;
a = temp / 10;
b = temp % 10;
sum = a + b;
temp = b * 10 + sum % 10;
if (temp == n)
break;
}
cout << cycle << endl;
return 0;
}
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int h, m;
cin >> h >> m;
if (m < 45)
{
if (h == 0)
{
h = 23;
}
else
{
h--;
}
m = 60 + m - 45;
}
else
m -= 45;
cout << h << ' ' << m << endl;
return 0;
}
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--)
{
int a, b;
cin >> a >> b;
// 주기가 있다.
b = !(b % 4) ? 4 : b % 4;
int ans = 1;
while (b--) ans *= a;
if (ans % 10 == 0) cout << "10\n";
else cout << ans % 10 << '\n';
}
return 0;
}
각 턴의 종료된 후에는 그 턴에서 구한 MST에서 가장 가중치가 작은 간선 하나를 제거합니다.
어떤 턴에서는 MST를 만들 수 없다면, 그 턴의 점수는 0점으로 처리합니다.
같은 간선이 여러 번 주어지는 경우는 없습니다.
정리하면 매 턴마다 MST를 구성했을 때, MST를 만들지 못한다면? 0으로 처리하고,
MST를 구성했다면 가중치들의 합을 리턴하는 방식으로 문제를 해결해야 합니다.
MST를 만들 수 없다는 뜻은 무엇일까요?
문제에서도 나와있듯이 [노드의 개수 != 간선의 개수 + 1] 이여야 합니다.
만약에 위의 조건을 만족했다면 우리는 MST를 만들었다는 뜻이 되기 때문입니다.
따라서 매턴마다 MST를 구성하고, MST 완성을 했다면 가중치들의 합을 출력하고,
간선들 중에서 가장 가중치가 작은 간선 하나를 제거하는 것은 쉽습니다.
기존에 가중치들을 오름차순으로 정렬했기 때문에 가장 앞쪽에 있는 간선이 제일 작은 가중치이기 때문이죠.
따라서 앞에 있는 가중치를 제거하고 다시 MST를 구상하면서 턴을 반복하면 됩니다.
소스 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 1001;
vector<pair<int, pair<int, int> > > edges;
int parent[MAX];
int N, M, K;
int findParent(int x)
{
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
void unionParent(int a, int b)
{
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
void input()
{
cin >> N >> M >> K;
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
edges.push_back({ i + 1,{a, b} });
}
sort(edges.begin(), edges.end());
}
void kruskal()
{
for (int i = 1; i <= N; i++) parent[i] = i;
int sz = static_cast<int>(edges.size());
int totalCost = 0;
int totalEdges = 0;
for (int i = 0; i < sz; i++)
{
int cost = edges[i].first;
int a = edges[i].second.first;
int b = edges[i].second.second;
if (findParent(a) != findParent(b))
{
unionParent(a, b);
totalCost += cost;
totalEdges++;
}
}
if (totalEdges + 1 == N)
cout << totalCost << ' ';
else
cout << "0 ";
// 가중치가 작은 간선을 제거
edges.erase(edges.begin());
}
void solve()
{
input();
while (K--)
{
kruskal();
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
그런데 금 빼빼로를 혜빈이까지 옮기기 위해서는 그만큼의 무게를 견디는 다리가 있어야 하는데요.
어떻게 하면 숭이가 혜빈이까지 움직일 수 있는지 구하는 게 이번 문제입니다.
우선은 최대한 금 빼빼로를 가져다가 주면 좋아하기 때문에, 최대한으로 설정해놓고 움직일 수 있도록 다리를 만들어야 합니다. 기존에 MST를 이용해서 어떻게 하면 최소한의 비용으로 모든 도시들을 연결한 방법이 있었는데, 이것을 반대로 생각해서 최대한의 비용으로 모든 도시들을 연결하게 설정합니다.
왜냐하면 우리는 금 빼빼로를 최대한으로 들고 가야하기 때문입니다.
최대한의 비용으로 그래프를 설계했다면 아래와 같을 것입니다.
노란색으로 색칠한 부분이 우리가 만든 최대의 비용으로 만든 그래프입니다.
이때 숭이가 1번 집에 있고, 혜빈이가 5번 도시에 있을 때 어떻게 하면 최대한 많은 금 빼빼로를 혜빈이에게 줄 수 있을까요?
우선은 혜빈이에게 갈려면 빨간색 선으로 되어있는 것처럼 7번 집, 6번 집, 5번 집을 거쳐가야 할 겁니다.
7번 집의 다리 내구도를 보니까 4까지 견딜 수 있고,
6번 집의 다리 내구도를 보니까 4까지 견딜 수 있고,
5번 집의 다리 내구도를 보니까 3까지 견딜 수 있네요.
즉 최대한 많은 금 빼빼로는 총 3개만 가져갈 수 있다는 것을 알았습니다.
4개를 가져가게 되면 6번 집에서 5번 집으로 갈 때 무너지겠죠.
어떻게 하면 이렇게 계산할 수 있을까요?
아까 위에서 우리는 MST를 최대 비용으로 집들을 연결했습니다.
1, 7을 연결할 때 두 집을 연결하는 과정에서 우리는 따로 인접 리스트 그래프를 한 개 더 만듭니다.
이 그래프는 얼마큼 금 빼빼로를 가져갈지 계산하기 위해서입니다.
그래서 두 그래프를 연결할 때마다 인접 리스트로 두 집의 양방향 연결을 만들어주고,
숭이 내 집에서 혜빈이 집까지 최소한의 비용으로 확인하면서 찾아가면 문제를 해결할 수 있습니다.
모든 집 들을 다리로는 나올 수 없는 987654321(무한대)형태로 초기화시킨 후,
숭이 내 집에서 출발해서 인접한 모든 집들을 확인하면서 더 싼 비용으로 갱신해나가면 됩니다.
이렇게 갱신해나가면 위의 빨간색 선분 처럼 우리는 1번 집에서 5번 집으로 갈 때 min(4, 4, 3)을 만나 결국 3이라는 값을 도출할 수 있습니다.
소스 코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 100001;
const int INF = 987654321;
int N, M, s, e;
vector<pair<int, pair<int, int> > > edges;
int parent[MAX];
vector<pair<int, int> > adj[MAX];
bool visit[MAX];
int dist[MAX];
bool compare(const pair<int, pair<int, int> >& a, const pair<int, pair<int, int> >& b)
{
return a.first > b.first;
}
int findParent(int x)
{
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
void unionParent(int a, int b)
{
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
void input()
{
cin >> N >> M >> s >> e;
for (int i = 0; i < M; i++)
{
int h1, h2, k;
cin >> h1 >> h2 >> k;
edges.push_back({ k, {h1,h2} });
}
}
void kruskal()
{
sort(edges.begin(), edges.end(), compare);
for (int i = 1; i <= N; i++) parent[i] = i;
int sz = static_cast<int>(edges.size());
vector<int> ans;
for (int i = 0; i < sz; i++)
{
int cost = edges[i].first;
int a = edges[i].second.first;
int b = edges[i].second.second;
if (findParent(a) != findParent(b))
{
unionParent(a, b);
adj[a].emplace_back(b, cost);
adj[b].emplace_back(a, cost);
}
}
}
void dijkstra()
{
fill(dist, dist + MAX, INF);
queue<int> q;
q.push(s);
visit[s] = true;
while (!q.empty())
{
int cur = q.front();
q.pop();
for (int i = 0; i < adj[cur].size(); i++)
{
int next = adj[cur][i].first;
int nextDistance = adj[cur][i].second;
if (visit[next]) continue;
visit[next] = true;
// 핵심: 금빼빼로를 최대한으로 들고가려고 할 때 그 무게를 견딜 수 있는 걸 찾아야하기 때문에
// 최소한 무게를 버틸 수 있도록 다리의 무게제한을 갱신한다.
dist[next] = min(dist[cur], nextDistance);
q.push(next);
}
}
// 중요한 점은 못갈 수 있다는 것
if (dist[e] == INF)
cout << "0\n";
else
cout << dist[e] << endl;
}
void solve()
{
input();
kruskal();
dijkstra();
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
모든 두 집 쌍에 대해서 불이 켜진 길로만 서로를 왕래할 수 있도록 해야 하며, 위 조건을 지키면서 절약할 수 있는 최대 액수를 구하는 문제입니다.
모든 두 집 쌍에 대해서 가로등을 켜면서(연결하면서) 최소의 비용으로 만들고 싶다면 MST를 구하라는 문제입니다.
그런데 절약할 수 있는 최대 액수를 물었으므로 [전체의 비용 - MST를 만드는 비용 = 최대 액수]로 구해주면 됩니다.
최종 비용을 계산할 때 보통은 최소의 비용을 구하라고 하지만 반대로 얼마큼 절약할 수 있는지를 물어보는 문제였습니다.
소스 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 200001;
int parent[MAX];
vector<pair<int, pair<int, int> > > edges;
int m, n, totalCost;
void input()
{
edges.clear();
totalCost = 0; // 전체 비용
for (int i = 0; i < n; i++)
{
int x, y, z;
cin >> x >> y >> z;
totalCost += z;
edges.push_back({ z, {x,y} });
}
sort(edges.begin(), edges.end());
for (int i = 1; i <= m; i++) parent[i] = i;
}
int findParent(int x)
{
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
void unionParent(int a, int b)
{
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
void kruskal()
{
int size = static_cast<int>(edges.size());
int useCost = 0; // MST 만드는 비용
for (int i = 0; i < size; i++)
{
int cost = edges[i].first;
int a = edges[i].second.first;
int b = edges[i].second.second;
if (findParent(a) != findParent(b))
{
unionParent(a, b);
useCost += cost;
}
}
cout << totalCost - useCost << endl;
}
void solve()
{
while (true)
{
cin >> m >> n;
if (m == 0 && n == 0) break;
input();
kruskal();
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 1001;
vector<pair<int, pair<int, int> > > edges;
int parent[MAX];
int N, M;
int findParent(int x)
{
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
void unionParent(int a, int b)
{
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
void input()
{
cin >> N >> M;
for (int i = 0; i < M; i++)
{
int a, b, c;
cin >> a >> b >> c;
edges.push_back({ c, {a,b} });
}
sort(edges.begin(), edges.end());
for (int i = 1; i <= N; i++) parent[i] = i;
}
void solve()
{
input();
int ans = 0;
for (int i = 0; i < edges.size(); i++)
{
int cost = edges[i].first;
int a = edges[i].second.first;
int b = edges[i].second.second;
if (findParent(a) != findParent(b))
{
ans += cost;
unionParent(a, b);
}
}
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
2. 그런데 마을을 하나의 마을로 연결하는 게 아니라 나는 두 마을로 쪼개고 싶다. 그래도 가능한 최소의 비용으로 하고 싶다.
마을을 하나의 최소한의 비용으로 연결하고 싶었다면 MST 알고리즘인 크루스칼 알고리즘을 사용하면 된다.
그런데 이 문제는 마을을 한 개가 아니고 두 개로 나누고 싶어하기 때문에 고민이 필요하다.
신기한 점은 MST를 이룰 때 노드의 개수가 N개면 최소한의 비용으로 연결하려면 간선의 개수는 N - 1개만 필요하게 된다. 예를 들어 노드 5개가 있을 때 4개의 간선만으로도 5개의 노드를 모두 연결할 수 있기 때문이다.
그러면 마을이 2개라면?
노드의 개수가 N개고, 간선의 개수는 N - 2개면 충분하다.
간선의 개수 N - 1개 까지는 마을 A에 연결시켜주고 마지막 간선만 딱 때어버리면 남겨진 마을이 곧 마을 B이기 때문이다.
가벼운 문제지만 살짝 깊이있는 질문을 하는 문제였다.
소스 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 100001;
int N, M;
vector<pair<int, pair<int, int> > > edges;
int parent[MAX];
int findParent(int x)
{
if (x == parent[x]) return x;
else return parent[x] = findParent(parent[x]);
}
void unionParent(int a, int b)
{
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
void input()
{
cin >> N >> M;
for (int i = 0; i < M; i++)
{
int a, b, c;
cin >> a >> b >> c;
edges.push_back({ c, {a,b} });
}
sort(edges.begin(), edges.end());
for (int i = 1; i <= N; i++) parent[i] = i;
}
void solve()
{
input();
int ans = 0;
int cnt = 0; // 간선 포함 개수
for (int i = 0; i < edges.size(); i++)
{
int cost = edges[i].first;
int a = edges[i].second.first;
int b = edges[i].second.second;
if (findParent(a) != findParent(b))
{
unionParent(a, b);
ans += cost;
cnt++;
// 마지막 간선을 제외한다.
if (cnt == N - 2)
break;
}
}
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
