본문 바로가기
카테고리 없음

백준알고리즘 1005번. ACM Craft

728x90

시간제한 때문에 꽤 까다로운 문제였습니다만,

결국 동적계획법 알고리즘을 숙달해서 풀었습니다.

지난번 피보나치 수열 때 유사 기술을 숙달했던게 도움이 되었군요 :)

문제와 조건은 그냥 링크로 걸어드리구요.

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;
}

 

728x90
반응형