N은 런타임 중에 입력되는 값이므로 아래처럼 정의하면 위험합니다.

int cost[N+1];

무작정 아이디어로 푸는 것보다는, 알고리즘을 찾아서 공부하시고 코드에 적용시키는걸 추천드려요.

위상정렬(topological sort)의 아이디어를 찾아서 공부하시면, 재귀함수를 쓰지 않고 풀 수 있습니다. 시간복잡도는 O(N+K)가 됩니다.

질문과는 상관없는 얘기지만, 저는 재귀로 풀었습니다. (풀리긴 풀려요.. 메모리 60MB정도에 시간은 850ms정도 나왔습니다.)

실례가 안된다면 혹시 그 방법 좀 알 수 있을까요??ㅠㅠ

제가 그 문제를 다시 들여다 보기엔 머리가 아프고.. ㅋ

그 당시 문제풀면서 풀었던 방식이랑 소스코드 정리해둔거 있는데 보내드릴까요?

아래는 그 당시 풀고나서 원노트에 끄적여뒀던 부분입니다. (도움이 될지는 모르겠네요;;)

별로 자랑할만한 코드도 안되고, dp 기본문제조차 제대로 못 풀던 때에 풀던거라 개판이긴하지만,

소스코드는 메일적어주시면 보내드릴게요.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

이번 문제를 푸는데만 2주가 넘게 걸렸다. 물론 하루종일 붙잡고 있었던 것도 아니고, 정확히 본시간으로 따지면 3일 정도 되겠지만, 아무튼 이 문제를 풀면서 재귀 함수를 만드는 방법에 대해 많이 배울 수 있었다.

먼저 DP문제를 보고 재귀함수를 구성할 땐, 맨 뒤에서 처음으로 오는 방향인지 맨 처음에서 맨 뒤로 가는 방향인지를 확실히 정해야 한다. 이 문제의 경우는 맨 뒤에서부터 맨 첫번째까지 오는 방향이었는데, 코딩을 할 때에는 반대 방향으로 짜야한다. 즉, 뒤에서 앞으로 오는 방향으로 문제를 풀려고 하면,  맨 뒤가 base case가 되고, 맨 앞에서 return되는 값이 실질적으로 main에서 해당 재귀함수를 호출 했을 때 얻게되는 return 값이 된다.

이 문제의 경우는 맨 뒤의 노드를 w라고 했는데,

나는 w부터 시작노드까지 거리를 구해나가는 방향으로 짜려고 했었고,

그래서 재귀함수의 경우는 w를 parameter로 받는 것이 아니라 시작노드를 parameter로 받아서 w까지 계속 타고 들어가도록 만들었다.

결국 각각의 재귀함수는 해당노드부터 w까지의 거리를 구해서 costFromCurToW[...]라는 배열에 저장함으로써 memoization을 이용하여 시간을 줄일 수 있었다.

이 문제에서는 고려해야할 테스트 케이스가 매우 많은데,

처음에  DP문제가 뭔지도 모르고 접근했을 때는 시작노드가 여러개인데 그 분기점까지의 깊이가 2이상인 경우를 생각하지 못했다. 예를 들면 다음과 같다.

(3은 공통된 부분인데, 어떻게 표현할 수가 없어서 그냥 2번 적었다. w는 [3]번 노드이다.)

여기서 답은 102가되는데, 멍청하게 풀었을 때엔 답이 12가 되버리게 만들었다.

그러다가 나중에는 0번 노드를 가짜로 만들고 cost[0]도 0이라고 가정했다.

그리고 시작노드가 모두 0번 노드에 연결되어있다고 가정했다. 결국 0번노드가 항상 시작노드가 되도록 만든 것이다.

이렇게 하고 나서도 문제는 계속 발생했었는데, 다른 문제 케이스의 경우는 다음과 같다

위의 경우에선, w가 [1]번 노드이므로 답이 10이 되어야 하는데 멍청하게 자꾸 1110이 답으로 출력되었다. 이 부분도 어떻게 어떻게 수정하고 나니까 이번에는 별 이상한게 또 문제가 됐다.

분기점이 아예 없이  [1]->[2], [3]->[4]와 같은 경우 w가 1일 때 cost[1]을 출력하는 것이 아니라 cost[3]+cost[4]를 자꾸 출력했기 때문이다.

이런것 말고도 몇개 더 있는데, 문제가 됐던 테스트 케이스는 아래에 통째로 올린다.

[[ INPUT ]]

19

3 2

100 100 100

1 2

2 3

1

3 2

100 100 100

1 2

2 3

2

11 10

10 100 1 1 1 5 8 9 7 1000 10

1 2

2 3

3 4

4 5

5 6

6 7

5 8

8 9

10 11

11 3

3

11 10

10 100 1 1 1 5 8 9 7 1000 10

1 2

2 3

3 4

4 5

5 6

6 7

5 8

8 9

10 11

11 3

4

11 10

10 100 1 1 1 5 8 9 7 1000 10

1 2

2 3

3 4

4 5

5 6

6 7

5 8

8 9

10 11

11 3

6

4 4

10 1 100 10

1 2

1 3

2 4

3 4

4

8 8

10 20 1 5 8 7 1 43

1 2

1 3

2 4

2 5

3 6

5 7

6 7

7 8

7

10 11

10 1 1 100 10 10 100 1 1 1

1 2

2 3

3 6

4 3

4 7

4 9

5 4

6 9

7 8

8 9

10 7

9

5 4

10 1 100 10 1000

5 2

1 3

2 4

3 4

4

7 6

1 100 10 1000 10 1 1

1 2

2 3

3 7

4 5

5 6

6 7

7

7 6

1 10 1 100 1 5 8

1 2

2 3

4 5

5 3

3 6

3 7

3

7 6

1 10 1 100 1 5 8

1 2

2 3

4 5

5 3

3 6

3 7

7

5 3

1 3 10 10 5

1 4

2 3

3 5

2

5 3

1 3 10 10 5

1 4

2 3

3 5

3

5 3

1 3 10 10 5

1 4

2 3

3 5

5

5 3

1 3 10 10 5

1 4

2 3

3 5

4

5 3

1 3 10 10 5

1 4

2 3

3 5

1

2 1

10

5

2 1

2

2 1

10

5

2 1

1

[[ ANSWER ]]

100

200

1011

1012

1018

120

39

212

1011

1012

102

110

3

13

18

11

1

5

15

·       마지막까지 문제가 됐던 테스트 케이스

위에서 6번 노드가 w였는데 6에 대한 cost값이 아닌 8->9 경로에 대한 cost값이 더해져서 결과값으로 나왔다.

(참고로 빨간색 숫자는 각 노드에 대한 cost값을 의미한다.)

아무튼 여기까지 다 해결하고 나니 다 잘 나오는거 같은데, 자꾸 틀렸다고 해서 queue<int> q[100001]로 선언한 STL 배열 q를 매번 초기화 시켜주니.. 드디어 맞았다.. ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

비록 시간도 많이걸리고 메모리도 엄청 잡아먹긴 했지만, 풀었다!!!!!!!!!

나중에 시간되면 남이 짠 코드 꼭 보고 넘어가야지...

정말정말 감사합니다 ㅠㅠ

Input

19
3 2
100 100 100
1 2
2 3
1
3 2
100 100 100
1 2
2 3
2
11 10
10 100 1 1 1 5 8 9 7 1000 10
1 2
2 3
3 4
4 5
5 6
6 7
5 8
8 9
10 11
11 3
3
11 10
10 100 1 1 1 5 8 9 7 1000 10
1 2
2 3
3 4
4 5
5 6
6 7
5 8
8 9
10 11
11 3
4
11 10
10 100 1 1 1 5 8 9 7 1000 10
1 2
2 3
3 4
4 5
5 6
6 7
5 8
8 9
10 11
11 3
6
4 4
10 1 100 10
1 2
1 3
2 4
3 4
4
8 8
10 20 1 5 8 7 1 43
1 2
1 3
2 4
2 5
3 6
5 7
6 7
7 8
7
10 11
10 1 1 100 10 10 100 1 1 1
1 2
2 3
3 6
4 3
4 7
4 9
5 4
6 9
7 8
8 9
10 7
9
5 4
10 1 100 10 1000
5 2
1 3
2 4
3 4
4
7 6
1 100 10 1000 10 1 1
1 2
2 3
3 7
4 5
5 6
6 7
7
7 6
1 10 1 100 1 5 8
1 2
2 3
4 5
5 3
3 6
3 7
3
7 6
1 10 1 100 1 5 8
1 2
2 3
4 5
5 3
3 6
3 7
7
5 3
1 3 10 10 5
1 4
2 3
3 5
2
5 3
1 3 10 10 5
1 4
2 3
3 5
3
5 3
1 3 10 10 5
1 4
2 3
3 5
5
5 3
1 3 10 10 5
1 4
2 3
3 5
4
5 3
1 3 10 10 5
1 4
2 3
3 5
1
2 1
10 5
2 1
2
2 1
10 5
2 1
1

Output

100
200
1011
1012
1018
120
39
212
1011
1012
102
110
3
13
18
11
1
5
15