시간제한 때문에 꽤 까다로운 문제였습니다만,
결국 동적계획법 알고리즘을 숙달해서 풀었습니다.
지난번 피보나치 수열 때 유사 기술을 숙달했던게 도움이 되었군요 :)
문제와 조건은 그냥 링크로 걸어드리구요.
https://www.acmicpc.net/problem/1005
처음에는 트리를 구성해서 큐로 풀어보려 했습니다만,
시간제한으로 문제가 안 풀리더라구요.
어떤 경우가 주어지더라도 1초 이내에 패스를 해야 하는 문제입니다.
아무리 별의 별 방법을 동원해도 안되던 찰나에 백준 사이트에 질문 답변을 참조하고서야 "동적계획법"이라는 방법을 사용한 "이모제이션"이라는 기법을 알게되었고 관련 기술을 숙달한 후에 직접 코딩으로 짜서 풀었습니다 :)
내공이 하나 늘어난 느낌이라 뿌듯하더라구요 ㅎㅎ
채점을 하면서 중간에 81%까지만 진행되고, 그 이후가 안 풀려서 헤메긴 했는데,
세상에나.. 건물 짓는 시간이 0초인 데이터도 있더라구요. ( 보이진 않지만 뻔합니다 )
그 부분을 해결하고 나서야 문제가 풀렸습니다.
크레이의 해설
이 문제는 소스 해설보다는 이해 위주로 진행하겠습니다.
동적계획법에 의한 이모제이션이란 분할정복이란 알고리즘의 초고속 버전입니다.
지난번 피보나치 수열과도 유사한 방법인데요.
아래와 같은 그래프가 본 문제의 2번째 샘플 데이터 구성입니다.
우리의 목적은 각 건물에 걸리는 시간을 모두 충족하고 나서라도 7번 건물을 1개 완공하는데 걸리는 시간을 구하는 것입니다.
이를 테면 4번 건물을 5초내에 지었다 하더라도 7번 건물을 지을 수 없습니다. 5번 건물도 완공이 되어야 하기 때문인데 이때는 8초가 걸리는 경로를 선택해야 합니다.
물론 깊이에 따라 총 걸리는 시간을 감안해야하지만요.
하여간 7번까지 오는 모든 경로중 가장 시간이 오래 걸리는
경로를 계산하면 풀리는 문제입니다.
분할정복으로 접근하면 아래와 같습니다.
7번 건물을 짓기 위해 기다려야 할 시간은
4번까지의경로와 5번까지의 경로 중
더 오래 걸리는 시간 입니다.
거기에 7번 건물 1개를 짓는 시간을 더하면 결국 7번 건물을 지을수 있는 총 시간이 되는 것이지요.
이를 이렇게 표현해볼까요?
완공시간(7) = 소요시간(4/5) 중 긴 시간 선택 + 건설시간(7)
완공시간(4) = 소요시간(2) + 건설시간(4)
완공시간(2) = 소요시간(1) + 건설시간(2)
완공시간(1) = 건설시간(1)
완공시간(5) = 소요시간(2) + 건설시간(5)
완공시간(2) = 소요시간(1) + 건설시간(2)
완공시간(1) = 건설시간(1)
목적지에서 역순으로 제일 시간이 많이 나오는 경로를 찾아, 찾아서 재귀 호출로 답을 구하는 방법인데, 코드 일부를 예로 들자면 아래와 같습니다.
long TimeCalc(int y)
{
long max=0, thistime;
// X->Y 그래프에서 도착지점 Y가 W인 모든 X
for(int x=1;x<=n;++x)
{
if(RuleXY[x][y])
{
thistime=TimeCalc(x);
if(thistime>max)max=thistime;
}
}
return max + BuildTime[y];
}그런데 이 방법은 문제가 있습니다.
중복되는 계산을 아주 많이 거치게 되는데 빨간 표시된 부분이 바로 중복계산에 해당하는 부분이고 실제 몇만건의 테스트 데이터에는 이런 건이 엄청나게 많은 것으로 보입니다.
완공시간(7) = 소요시간(4/5) 중 긴 시간 선택 + 건설시간(7)
완공시간(4) = 소요시간(2) + 건설시간(4)
완공시간(2) = 소요시간(1) + 건설시간(2)
완공시간(1) = 건설시간(1)
완공시간(5) = 소요시간(2) + 건설시간(5)
완공시간(2) = 소요시간(1) + 건설시간(2)
완공시간(1) = 건설시간(1)
너비 탐색 방식보다도 훨씬 많은 시간이 소요되어 결국 시간 내에 풀 수 없습니다.
그렇다면 방법이 있을까요?
물론 있습니다. 지난 피보나치와 똑같은 원리로 계산한 부분을 저장해놓았다가,
다음번에 똑같은 경우를 만나면 재귀호출을 하지 않고 저장한 값을 사용하는 것입니다.
사실 이 소스를 세세하게 설명드리려면 꽤 많은 면을 할애해야 하기 때문에 주석을 달아놓은 소스로 마무리짓겠습니다. 혹시 이해가 어려운 부분 있으시면 해당 부분 질문 주시면 답변드리겠습니다. 크레이도 오늘에서야 이 기법이 확실히 이해되었습니다 :)
여기까지 읽어주셔서 감사합니다.
소스코드
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int t, n, k; // 테스트케이스, 건물, 규칙
// 각 건물의 소요시간 ( 1 ~ 100000 )
long BuildTime[1001];
// 각 건물의 총 소요시간 메모
long BuildMemo[1001];
// 건물 X->Y 이동 그래프 ( [X][Y] )
int RuleXY[1001][1001];
long TimeCalc(int y)
{
if(BuildMemo[y]>=0)return BuildMemo[y];
long max=0, thistime;
// X->Y 그래프에서 도착지점 Y가 W인 모든 X
for(int x=1;x<=n;++x)
{
if(RuleXY[x][y])
{
if(BuildMemo[x]>=0)thistime=BuildMemo[x];
else thistime=TimeCalc(x);
if(thistime>max)max=thistime;
}
}
return BuildMemo[y]= max + BuildTime[y];
}
void Result()
{
scanf("%d", &t);
while (t--)
{
scanf("%d %d", &n, &k);
// 고속초기화
memset(BuildTime, 0, sizeof(long) * 1001);
memset(BuildMemo, -1, sizeof(long) * 1001);
memset(RuleXY, 0, sizeof(int) * 1001*1001);
// 건물의 소요시간을 읽어 입력
for(int i=1;i<=n;++i)
scanf("%d", BuildTime+i);
// 건물X에서y로 가는 규칙
int rule_x, rule_y;
// 주어지는 규칙수만큼 반복하며
for(long i=1;i<=k;++i){
scanf("%d %d",
&rule_x, &rule_y);
RuleXY[rule_x][rule_y]=1;
}
// 목적지 w 읽음
int w;
scanf("%d", &w);
long totaltime = TimeCalc(w);
printf("%ld\n", totaltime);
}
}
int main()
{
Result();
return 0;
}