✅ 한 것들
- 백준
⚔️ 백준
- 9095 1,2,3 더하기
1504 특정한 최단 경로
#include<iostream>
#include<vector>
#include<queue>
#include<tuple>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<vector<pii>> vvp;
namespace
{
void djk(int from, vi& dVec, vvp& graph)
{
// pq에서 노드 꺼내면서 간선들로 최솟값 갱신
// 최솟값 갱신되면 pq에 넣기
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0,from});
dVec[from] = 0;
while (!pq.empty())
{
int fullDist, toNode;
tie(fullDist, toNode) = pq.top(); pq.pop();
if (fullDist != dVec[toNode]) continue;
for (pii edge : graph[toNode])
{
int dist, newNode;
tie(dist, newNode) = edge;
if (dVec[newNode] != -1 &&
dVec[newNode] <= fullDist + dist) continue;
dVec[newNode] = fullDist + dist;
pq.push({dVec[newNode], newNode});
}
}
}
}
// 만약 a를 지날 때 이미 b를 지나쳤다면, a에서 b로 다시 갈 필요가 없다
// 1->b + b->a가 1->a와 같다면, 1->N은 1->a->N 만으로 된다는 뜻
int main()
{
// 1,a,b에 대해 다익스트라
// 1 a b N 혹은 1 b a N을 비교
cin.tie(nullptr);
int N, E, start, end, dist, nodeA, nodeB;
cin >> N >> E;
vvp graph = vvp(N+1);
for(int i=0; i<E; i++)
{
cin >> start >> end >> dist;
graph[start].push_back({ dist, end });
graph[end].push_back({ dist, start });
}
cin >> nodeA >> nodeB;
vi dfromS = vi(N+1, -1);
vi dfromA = vi(N+1, -1);
vi dfromB = vi(N+1, -1);
djk(1, dfromS, graph);
djk(nodeA, dfromA, graph);
djk(nodeB, dfromB, graph);
int cost1, cost2;
if (dfromS[nodeA] + dfromA[nodeB] == dfromS[nodeB])
cost1 = dfromS[nodeB] + dfromB[N];
else
cost1 = dfromS[nodeA] + dfromA[nodeB] + dfromB[N];
if (dfromS[nodeB] + dfromB[nodeA] == dfromS[nodeA])
cost2 = dfromS[nodeA] + dfromA[N];
else
cost2 = dfromS[nodeB] + dfromB[nodeA] + dfromA[N];
int mincost = min(cost1, cost2);
bool cantA, cantB, cantN;
cantA = dfromS[nodeA] == -1;
cantB = dfromS[nodeB] == -1;
cantN = dfromS[N] == -1;
if (cantA || cantB || cantN) cout << -1;
else cout << mincost;
}- 다익스트라할 때 pq에 넣는 건 간선 비용이었으면서 최종 비용으로 해석해버려서 틀림
- 넣는 걸 최종 비용으로 바꿔줘서 맞았습니다 띄움
#include<iostream>
#include<vector>
#include<queue>
#include<tuple>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<vector<pii>> vvp;
const int INF = 1e8;
namespace
{
void djk(int from, vi& dVec, vvp& graph)
{
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0,from});
dVec[from] = 0;
while (!pq.empty())
{
int fullDist, toNode;
tie(fullDist, toNode) = pq.top(); pq.pop();
if (fullDist != dVec[toNode]) continue;
for (pii edge : graph[toNode])
{
int dist, newNode;
tie(dist, newNode) = edge;
if (dVec[newNode] <= fullDist + dist) continue;
dVec[newNode] = fullDist + dist;
pq.push({dVec[newNode], newNode});
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
int N, E, start, end, dist, nodeA, nodeB;
cin >> N >> E;
vvp graph = vvp(N+1);
for(int i=0; i<E; i++)
{
cin >> start >> end >> dist;
graph[start].push_back({ dist, end });
graph[end].push_back({ dist, start });
}
cin >> nodeA >> nodeB;
vi dfromS = vi(N+1, INF);
vi dfromA = vi(N+1, INF);
vi dfromB = vi(N+1, INF);
djk(1, dfromS, graph);
djk(nodeA, dfromA, graph);
djk(nodeB, dfromB, graph);
int cost1 = dfromS[nodeA] + dfromA[nodeB] + dfromB[N];
int cost2 = dfromS[nodeB] + dfromB[nodeA] + dfromA[N];
int mincost = min(cost1, cost2);
if (mincost >= INF) cout << -1;
else cout << mincost;
}- 근데 왜 또 느린가 봤더니 cin.tie()만으로는 io 최적화 못하고, sync_with_stdio도 설정해줘야 했음
- dfromS가 == INF인 걸로 확인하지 않고 최종 비용이 INF보다 큰지 확인하는 걸로 대체
- INF를 1e9로 선언하면 오버플로우 나서 틀렸음. 1e8로 내렸더니 맞음.
- 위 주석에서
만약 a를 지날 때 이미 b를 지나쳤다면, a에서 b로 다시 갈 필요가 없다이 부분 체크 안해줘도 됐다.- 그 경우엔 b로 간 후 a로 가는게 최저 비용일 테니까. 굳이 또 검증해줄 필요 없다.
15486 퇴사 2
#include"15486.h"
using namespace std;
typedef pair<int, int> pii;
namespace
{
int N;
vector<pii> calendar;
vector<int> cache;
int maxPay(int day)
{
if (day > N) return 0;
if (cache[day] != -1) return cache[day];
int time, pay;
tie(time, pay) = calendar[day];
int p1 = maxPay(day + 1);
int p2 = pay + maxPay(day + time);
if (day + time - 1 > N) p2 = 0;
int maxp = max(p1, p2);
cache[day] = maxp;
return maxp;
}
}
void B15486::Solution()
{
int T, P; // T : 소요 기간, P : 받는 금액
cin >> N;
cache = vector<int>(N + 1, -1);
calendar.push_back({ 0,0 });
for (int i = 0; i < N; i++)
{
cin >> T >> P;
calendar.push_back({ T,P });
}
cout << maxPay(1);
}풀긴했는데 메모리가 높게 나오고 코드도 길다
void B15486::Solution()
{
ios::sync_with_stdio(false);
int N, T, P; // T : 소요 기간, P : 받는 금액
cin >> N;
vi t, p, d;
t = vi(N + 2), p = vi(N + 2), d = vi(N + 2);
for (int i = 1; i <= N; i++) cin >> t[i] >> p[i];
for (int i = 1; i <= N; i++)
{
// 전날까지의 결과와 당일 끝나는 작업이 반영된 결과 비교
d[i] = max(d[i - 1], d[i]);
// N일차에 1일 걸리는 작업까지만 가능
if (i + t[i] <= N + 1)
// 이전까지의 결과와 오늘 작업 결과를 비교
d[i + t[i]] = max(d[i + t[i]], d[i] + p[i]);
}
// N일차에 1일짜리 작업을 했다면 d[N+1]이 필요
cout << max(d[N],d[N+1]);
}다른 풀이 베끼며 주석 작업
앞에서 시작하는 dp : 해당 날짜가 됐을 때 벌 수 있는 최대 금액
void B15486::Solution()
{
ios::sync_with_stdio(false);
int N;
cin >> N;
vi t, p, d;
t = vi(N + 2), p = vi(N + 2), d = vi(N + 2);
for (int i = 1; i <= N; i++) cin >> t[i] >> p[i];
// 뒤에서 시작하는 dp
for (int i = N; i >= 1; i--)
{
int e = i + t[i];
if (e <= N + 1)
// i일차부터 끝날 때까지 얻을 수 있는 최대 금액
// 당일 일을 했을 경우와 안 했을 경우를 비교한다
d[i] = max(d[e] + p[i], d[i + 1]);
else
// 당일 일을 시작했을 때 기한 안에 끝나지 못하면 그냥 안 한다
d[i] = d[i + 1];
}
cout << d[1];
}뒤에서 시작하는 dp : 해당 날짜 포함하여 남은 날 동안 벌 수 있는 최대 금액
5557 1학년
#include"5557.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
namespace
{
int N, num;
vi nums;
vvl dp;
ll fn(int curIdx, int curSum)
{
if (curIdx == N - 1)
{
if (curSum == nums[curIdx]) return 1;
else return 0;
}
if (dp[curIdx][curSum] != -1) return dp[curIdx][curSum];
ll s1 = 0, s2 = 0;
if (curSum - nums[curIdx] >= 0)
s1 = fn(curIdx + 1, curSum - nums[curIdx]);
if (curSum + nums[curIdx] <= 20)
s2 = fn(curIdx + 1, curSum + nums[curIdx]);
dp[curIdx][curSum] = s1 + s2;
return s1 + s2;
}
}
void B5557::Solution()
{
// 최종 결과가 마지막 수가 되어야 하고
// 중간 결과는 음수가 되면 안된다
// 중간 결과 기준으로 해당 수를 만들 수 있는
// 경우의 수가 몇 개 있는지 찾는다
cin >> N;
nums = vi(N);
dp = vvl(N, vl(21,-1));
for (int i = 0; i < N; i++)
cin >> nums[i];
cout << fn(1, nums[0]);
}- fn(0,0)으로 시작해서 틀렸었다
#include <iostream>
#include <vector>
using namespace std;
long long N, arr[100];
vector<long long> dp(21);
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) cin >> arr[i];
dp[arr[0]] = 1;
for (int i = 1; i < N - 1; i++) {
vector<long long> tmp(21);
for (int j = 0; j < 21; j++) {
if (!dp[j]) continue;
if (j + arr[i] < 21) tmp[j + arr[i]] += dp[j];
if (j - arr[i] >= 0) tmp[j - arr[i]] += dp[j];
}
dp.swap(tmp);
}
cout << dp[arr[N - 1]] << '\n';
}https://www.acmicpc.net/source/98437289
앞에서부터 쌓아나가면서 '특정 수를 만들어내는 경우의 수'를 쌓아나간다는 식으로 생각하면,
즉, 상향식 dp를 한다면 좀 더 코드가 간결해진다.
4803 트리
#include"4803.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
void B4803::Solution()
{
int n, m, node1, node2, count = 0;
while (true)
{
count++;
cin >> n >> m;
if (n == 0 && m == 0) break;
vvi graph = vvi(n+1);
vb visited = vb(n + 1);
vi parent = vi(n + 1);
while (m--)
{
cin >> node1 >> node2;
graph[node1].push_back(node2);
graph[node2].push_back(node1);
}
int T = 0;
for (int i = 1; i <= n; i++)
{
if (visited[i]) continue;
queue<int> q;
q.push(i);
visited[i] = true;
parent[i] = i;
bool hasCycle = false;
while (!q.empty())
{
int f = q.front(); q.pop();
for (int node : graph[f])
{
if (visited[node])
{
if(node != parent[f])
hasCycle = true;
continue;
}
visited[node] = true;
parent[node] = f;
q.push(node);
}
}
if (!hasCycle) T++;
}
cout << "Case " << count << ": ";
if (T == 0) cout << "No trees.";
else if (T == 1) cout << "There is one tree.";
else if (T > 1) cout << "A forest of " << T << " trees.";
cout << '\n';
}
}방향 그래프는 dfs 끝나기 전에 재방문하면 사이클 성립
무향 그래프는 dfs 끝나기 전에 재방문했는데 부모 노드도 아니면 사이클 성립
너 정말 **핵심**을 찔렀어