Study/CODINGTEST
[1005]ACM craft
ExcellEast
2022. 2. 12. 13:37
처음에는 다익스트라 알고리즘의 변형으로 문제를 풀려고 하였다. 알고리즘을 짜는데 상당히 오랜 시간이 걸렸지만(stl 등의 c++ 사용법을 익히는 등의 이유로) 정답은 얼추 잘 맞추는거 같았다. 하지만 메모리 초과 문제가 발생하였다.
초안:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
short times = 0;
cin >> times;
for (int t = 0; t < times; t++)
{
vector<short> relations[1001];
int result_cost[1001];
int costs[1001];
priority_queue<pair<short, int>, vector<pair<short, int>>, less<pair<short, int>>> pq;
int nob = 0, nor = 0;
cin >> nob >> nor;
for (int i = 1; i <= nob; i++)
{
cin >> costs[i];
result_cost[i] = costs[i];
}
for (int i = 0; i < nor; i++)
{
int n = 0, m = 0;
cin >> n >> m;
relations[n].push_back(m);
}
short end_point = 0;
cin >> end_point;
pair<int, short> p = make_pair(costs[1], 1);
pq.push(p);
while (!pq.empty())
{
pair<int, short> current_point = pq.top();
pq.pop();
for (auto& ele : relations[current_point.second])
{
if (result_cost[current_point.second] + costs[ele] > result_cost[ele])
{
result_cost[ele] = result_cost[current_point.second] + costs[ele];
}
pq.push(make_pair(result_cost[ele], ele));
}
}
if (costs[end_point] > result_cost[end_point])
result_cost[end_point] = costs[end_point];
cout << result_cost[end_point];
}
}
이번엔 동적 프로그래밍을 활용하여 풀기로 하였다. 처음부터 코드를 스스로 짠 건 아니고 다른 사람이 풀은 걸 보고 떠올려서 작성해보았다. 이 코드가 보여주는 동적 프로그래밍의 특징은 테이블을 만들어서 거기에 기록한다는 점이다. 테이블에 기록된 작은 문제의 값을 이용하여 보다 큰 sub problem도 해결해나갈수 있다는 점도 그렇다.
#include <bits/stdc++.h>
using namespace std;
int times = 0;
int b,k,n,m,e,dp[1001];
int arr[1001];
bool path[1001][1001];
int func(const int& a){
if(dp[a] != -1) return dp[a];
int mt = 0;
for(int i = 1; i <= b; i++)
{
if(path[i][a] != true) continue;
mt = max(mt, func(i));
}
dp[a] = mt + arr[a];
return dp[a];
}
int main(){
cin >> times;
while(times--)
{
memset(dp, -1, sizeof(dp));
memset(arr, 0, sizeof(arr));
memset(path, false, sizeof(path));
cin>> b >> k;
for(int i = 1; i <= b; i++)
cin>>arr[i];
for(int i = 0; i < k; i++)
{cin>> n >> m;
path[n][m] = true;
}
cin >> e;
cout << func(e) << endl;
}
}