문제 개요
오늘의 코딩 테스트 문제는 백준의 ACM Craft였다. 게임 개발 시뮬레이션 문제로, 건물 건설 순서와 시간을 고려해 최적의 건설 시간을 계산하는 문제다.
문제 분석
문제의 핵심은 다음과 같다:
1.
건물마다 건설에 필요한 선행 건물이 있다.
2.
여러 건물을 동시에 건설할 수 있다.
3.
특정 건물을 짓는 데 걸리는 최소 시간을 계산해야 한다.
처음엔 단순하게 접근했다가 시간 초과로 실패했다. 문제를 다시 읽어보니 동적 계획법(DP)을 사용해야 한다는 걸 깨달았다.
접근 방식
1.
각 건물별로 선행 건물 목록을 저장한다.
2.
재귀적으로 선행 건물들의 건설 시간을 계산한다.
3.
현재 건물의 건설 시간 + 선행 건물 중 가장 오래 걸리는 시간을 합산한다.
코드 구현
#include <iostream>
#include <vector>
using namespace std;
vector<int> D;
vector<int> dp;
vector<vector<int>> requires;
int getDP(int n)
{
int max_time = 0;
for (int node: requires[n])
{
if (dp[node]<0)
{
getDP(node);
}
max_time = max(max_time, dp[node]);
}
dp[n] = D[n] + max_time;
return dp[n];
}
int main()
{
int T, N, K;
cin >> T;
vector<int> results(T);
for (int t = 0; t < T; t++)
{
cin >> N >> K;
D.clear();
for (int i = 0; i < N; i++)
{
int temp;
cin >> temp;
D.push_back(temp);
}
vector<pair<int, int>> edges(K);
for (int i = 0; i < K; i++)
cin >> edges[i].first >> edges[i].second;
int W;
cin >> W;
requires.clear();
for (int i = 0; i < N; i++)
{
vector<int> require;
for (int j = 0; j < K; j++)
if (edges[j].second == i+1)
require.push_back(edges[j].first-1);
requires.push_back(require);
}
dp.clear();
for (int i=0; i<N; i++)
dp.push_back(-1);
results[t] = getDP(W-1);
}
for (int result : results)
cout << result << endl;
return 0;
}
C++
복사
주요 로직은 getDP 함수에 있다. 이 함수는 재귀적으로 각 건물의 최소 건설 시간을 계산한다. 메모이제이션을 사용해 중복 계산을 방지했다.
문제 해결 과정
처음에는 벡터만 사용해서 구현했다가 시간 초과가 발생했다. DP를 적용하고 나서야 해결할 수 있었다. 역방향 의존성(즉, 어떤 건물이 현재 건물의 선행 건물인지)을 처리하는 것도 까다로웠다. 결국 재귀 함수로 이 문제를 해결했다.
회고
1.
DP 문제임을 빨리 캐치하지 못한 게 아쉽다. 문제 유형을 좀 더 빨리 파악할 수 있도록 연습해야겠다.
2.
코드의 가독성과 효율성 사이의 균형을 잡는 게 여전히 어렵다. 헤매면서 수정하다보니 너무 지저분하게 작성했다.
이번 문제를 통해 DP의 중요성을 다시 한번 느꼈다. 알고리즘의 선택이 성능에 얼마나 큰 영향을 미치는지 직접 경험할 수 있었다. 앞으로도 꾸준히 알고리즘 문제를 풀면서 실력을 키워나가야겠다.
