BOJ 2311 왕복 여행

mcmf로 풀 수 있는 문제이다.
1 -> N -> 1 에 소요되는 최소 시간을 구해야 하는데, 한 번 지나간 길은 다시 갈 수 없다.
한 번 지나간 길을 다시 갈 수 없다는 것을 각 길에 대해서 capacity를 1로 놓음으로써 해결할 수 있고, 왕복하는 것은 src->1->N->sink 에서 src->1, N->sink 의 capacity를 2로 놓음으로써 1에서 N까지 각 길을 한 번만 거치고 갈 수 있는 두 가지 경로를 구하는 것과 왕복하는 경로와 같다는 것을 이용해서 푼다. 정말 멋진 풀이다...

그런데, 양방향 간선인 점에서 좀 헷갈리는 부분이 있었다. 양방향 간선이므로 양방향으로 capacity를 1씩 주게 되는데, 그렇게 되면 한 번 지나간 길을 반대 방향으로 한 번 더 지나가게 될 수 있지 않을까? 라는 생각이 들었다.

오랜 고민 끝에, 그럴리 없다는 것을 알게 되었다. 바로 한 번 지나간 길(cost)의 반대 방향의 residual capacity는 1이되고 코스트는 -cost이다. 그렇기 때문에 capacity가 1이고 cost인 것을 선택하지 않고 -cost인 것을 선택하게 될 것이다.(mcmf에서는 bfs나 dfs가 아닌 최단 거리를 구하는 알고리즘으로 augment path를 찾기 때문에!) 즉, 만약 한 번 지나간 길의 반대 방향으로 한 번 더 지나가게 된다면 사실 그것은 한 번 더 지나가는 것이 아니라 상쇄하는 것이 된다. 즉, 그 길은 지나가지 않은 셈 치게 되는 것이다.

이 문제로 인해 좀 network flow에 대해 좀 더 이해할 수 있었다.

그리고 mcmf를 사용하지 않고도 풀 수 있는 방법이 있다. appa님이 질문게시판에 소개한 방법인데, 생각해보면 network flow의 원리와 비슷한 것 같기도 하고, 정말 멋있는 방법이다. 링크 -> https://www.acmicpc.net/board/view/8285
-1을 곱하는 것은 N에서 1로 가는 경로를 찾을 때, 어떤 길을 가지 않은 셈 치는, 즉 상쇄하는 효과를 주는 것 같다.

직접 예제를 가지고 해보면 이해가 더 빠르다.

내가 사용했던 예제
5 8
1 4 1
4 3 1
1 2 1
2 3 1
3 5 1
2 5 3
1 5 10
5 4 10

답은 7

BOJ 9576 책 나눠주기

이 문제는 greedy 로 풀어야 한다.

일단 이분 매칭으로 풀어도 풀리긴 하는데 시간이 매우 오래 걸리고... O(VE) 이므로 데이터가 빡빡하게 들어오면 시간초과가 날 것 같다.

일단 greedy... 생각을 많이, 신중하게 하고 확실한 근거를 가지고 해야 하는데 대충 짐작으로 짰더니 틀렸다. 그리고 한 동안 왜 틀렸는지도 전혀 깨닫지 못했다... (애초에 내가 푼 방법에 대한 명확한 근거가 없었으니...)

(a번, b번)을 sorting하되 a번을 기준으로 sorting하고 a값이 같은 경우 b를 기준으로 sorting해서 앞에서부터 하나씩 선택하는 식으로 했는데, 반례를 찾았다.

1 ->test case 개수

3 3 -> n, m

//a, b값

1 3 

1 3

2 2

인 경우 이다. 생각해보면... 어렵다.

일단 드는 생각이... 그렇다면, b-a값이 작은 순으로 sorting을 해야하는 것인가?

몇몇 분의 코드를 봤는데 기억나는 코드가 b값을 기준으로 sorting하고, b값이 같으면 a값을 기준으로 sorting한 것 같은데... 이렇게 해도 되는 것인지 확실하게 입증을 못하겠다.

물론 b-a값이 작은 순으로 한다고 해서 맞는 것인지도 확실하게 증명은 못 하겠다.

일단 제출해 봐야겠다.... 틀렸다...

반례가 있는 것인가... 반례는 비교적 빨리 찾을 수 있었다.

n : 4, m : 4

//a, b값

1 1

2 2

1 3

3 4

인 경우이다. 일단 1 1, 2 2 인 경우를 먼저 처리하고 3 4를 처리할 때, 내 코드에서는 앞에 것을 먼저 선택하기 때문에 3을 선택하게 되고, 자연히 뒤에 오는 1 3을 처리할 때 아무 것도 선택할 수 없게된다. 

그렇다고 뒤에서부터 선택하는 것은 해결책이 될 수 없다. 유사한 반례가 생긴다.

그리고 다른 분 코드를 봤는데, 

b값을 기준으로 오름차순 sorting, b값이 같을 경우 a값 기준으로 내림차순 sorting...

일단 나중에 좀 더 공부하고 다시 풀어 봐야겟다...

BOJ 12785 토쟁이의 등굣길

토쟁이가.... 등교하면서 토스트를 사먹어서 토쟁이였다!!!

항상 최단 거리로 가야하고, 토스트 가게를 거쳐가야 하므로... 이 문제는
초, 중 학교 수학시간에 자주 본 문제같다.

즉 (집에서 토스트 가게까지의 경로의 수 * 토스트 가게에서 학교까지의 경로의 수) 가 답이 될 것인데, 예전에 이런 걸 계산할 때 보면 1, 1, 을 가장자리에 적어놓고 더하고 또 더하는 식으로...
즉, d[x][y] = d[x-1][y] + d[x][y-1] 로 나타낼 수 있겠다.

한 번 코드를 짜봐야겠다.
결국 AC를 받긴했는데... 좀 틀렸다.
long long값이 나오는 것과, x, y의 각각의 길이에 맞게 초기화를 잘 해줘야 하는데 x에 해당하는 길이만 초기화 한 것도 문제였다...

BOJ 1049 기타줄

기타줄이 N개 필요한데, 기타줄을  6개씩 묶어서 팔거나 낱개로 팔기도 한다.
6개씩 묶어서 파는 가격과 낱개의 가격이 주어질 때, 기타줄을 적어도 N개 사기 위해 필요한 돈의 최소값을 구하는 문제이다.

N개만 사는 최소 비용을 구하는 문제라면 동전dp처럼 풀면 될 것 같은데... 음 이건 N개 이상을 사는 최소 비용을 구하는 문제라고 볼 수 있으니
d[N] = N개 이상의 기타줄을 구매하기 위해 필요한 최소 비용 ...
음... 문제 분류를 얼떨결에 봐버렸다.
그리디 알고리즘으로 돼있다... 아...

그렇다. 다시 생각해보니 굳이 dp를 쓸 필요가 없다...
지금 브랜드 별로 6개짜리 묶음 가격과 낱개 가격이 주어지는데, 6개 묶음 가격중에서, 낱개 가격중에서 각각 제일 싼 가격을 택하면 된다.
즉, 이 문제는 6개 묶음 가격과 낱개 가격이 하나씩만 주어지는 문제가 되는 것이다.

그리고 6개 묶음 가격이 낱개로 했을 때는 얼마인지 보고, 6개 이상의 기타줄에 대해서는 낱개로 사는 것이 나은지 6개묶음으로 사는 것이 나은지 판단해본다.

그리고 낱개로 사는 것이 더 낫다면 바로 답을 구할 수 있을 것이고,
그게 아니라면 좀 더 생각해 봐야한다.
6개묶음으로 사는 것이 더 쌀 경우 N이 6의 배수라면 답이 나올 것인데, 그렇지 않다면 좀 더 생각해 봐야한다.

N이 6의 배수가 아니라면
 (N/6+1) * (묶음 가격) 이 더 싼지, (N/6) * (묶음 가격) + (N%6) * (낱개 가격) 이 더 싼지 비교해봐서 답을 구하면 될 것이다.

LeetCode OJ - 446. Arithmetic Slices II - Subsequence

N개의 숫자로 구성된 수열이 주어지면 그 수열의 부분 수열(연속되지 않아도 되고 순서만 맞게 선택되면 된다.)이면서 등차 수열인 수의 개수를 구하는 문제이다.

dp로 풀어야 한다.
d[cur][pre] = 현재 수가 arr[cur]이고 이전의 수가 arr[pre]인 경우의 등차 수열인 부분 수열의 개수

입력으로는 서로 다른 오름차순의 수가 들어오는 것 같으니...(해석을 잘 못해서 정확치는 않다.)
d[cur][pre] = pre-ppree==cur-pre 인 경우, d[pre][ppre]+1 (원래 ....pppre-ppre-pre-cur 로 이루어진 수열의 개수와 ppre-pre-cur 수열의 1개를 더해준 것)

근데 이렇게 할 경우 O(N의 세제곱)정도의 시간복잡도가 나오기 때문에 좀 힘들어보인다... 일단 C++로는 99개의 테스트 케이스 대부분을 통과했지만 내 기억으로는 98번째 데이터에서 시간초과를 받았다. 그런데 그 코드를 그대로 자바 코드로 옮겨서 제출했더니 통과했다...

음.. 일단 이 문제 관련 discussion 게시판에 가서 O(N제곱)이 걸리는 풀이를 봤다.
힌트에는 binary tree라고 되어있었는데... 보니까 map을 쓰는 것이었다.
그럼 정확히는 O(N제곱*logN)인가... 여튼, 예전에 이런 식으로 푸는 문제를 본 적이 있는 것 같은데...  전혀 생각도 못했다.

d[cur][by] = arr[cur]를 마지막으로 하고 차이가 by인 등차수열의 개수
로 하는 것 같다. 이 방법은 사실 처음에 생각했던 방법인데, 차이값이 최대 int형 범위까지 나올 수 있어서 너무 크기 때문에, 그리고 음수가 나올 수도 있기 때문에 배열을 못 잡을 것이라고 생각했다... 아 그런데 map이 있었지... map을 이용한 dp... 예전에 풀었던 것 같은데... 그래도 지금이라도 봤으니 다행이다.

d[cur][by] = SUM(arr[cur]-arr[pre]==by인 pre에 대하여, d[pre][by]+1)
이 될 것이다.
그리고 by는 최대 N개가 나올 수 밖에 없으므로 모든 수에 대해 다 돌리지 말고 N개의 by에 대해서만 보면 된다.

이게 구현하는 과정에서 좀 고려해야할 것이 있다. 이 문제에서 요구하는 등차수열은 길이가 3이상이어야 한다. 그렇기 때문에 길이가 2인 등차수열을 잘 처리해줘야 하는데...
1, 1, 2, 3 이 주어지면 아마 1, 2, 3을 두 개 만들 수 있으므로 2가 나와야 하는데 나는 보통은 두 개 짜리의 개수는 항상 0으로 처리해서 이 경우 1이 나왔다.
그리고 최종 답은 cur, by에 대해 모든 경우를 다 더해봐야 하는데, 두 개인 경우가 0일 때는 괜찮았는데, 두 개인 경우도 개수를 부여하면 이제는 두 개인 경우가 뭔지 구분을 해야하는데... 어렵다..

그래서 고민 끝에 재귀로 한 번 짜보기로 했다. 재귀로 해도 여전히 어렵다...

결국 다시 discussion의 정답 코드를 분석해보다가 이해했다.
지금 문제가 두 개인 경우는 등차수열이 아니기 때문에 0으로 처리할 경우 1, 1, 2, 3 같은 예제에서 cur==2, by==1일 때 경우의 수가 0이되어 답이 1이 나오게 되는 것인데...
(문제를 다시 잘 읽어보면 1, 2, 3이라고 경우의 수가 1이 되는 것이 아니다. 인덱스상으로 1, 2, 3은 두 가지가 나온다. 문제에서는 인덱스를 기준으로 해서 등차수열의 개수를 구하라고 하고 있다.) 정답 코드들은 길이가 2인 경우를 0으로 치지 않고 개수가 있는 것으로 친다. 즉, 길이가 2인 경우도 센다(count한다).
그러면 또 위에서 고민했던 두 개인 경우가 뭔지 구분해서 최종 답에는 합산하지 않아야 한다. 하지만 그렇게 처리하지 않는다. 등차수열이 되는 경우를 보자. 길이가 3인 어떤 등차수열X의 개수는 (수열X에 포함되는 길이가 2인 등차수열 개수)들의 합이된다. 결국 길이가 3인 등차수열의 개수를 구하면서 최종 답 ans 변수에는 길이가 3인 등차수열의 개수를 구할 때 이용되는 길이가 2인 등차수열의 개수를 더해준다.
그리고 코드상으로는 길이가 3인 등차수열의 개수에 +1을 해준다.
그렇다면 길이가 3인 등차수열의 개수는 어디에 쓸까? 바로 길이가 4인 등차수열의 개수를 구할 때 쓸 것인데, 이제 여기서부터는.. 길이가 4인 등차수열의 개수는 (길이가 3인 등차수열 개수 + 1) 들의 합이다. +1이 의미하는 것은 길이가 하나 늘어나면서 끝에서부터 길이가 3개짜리인 등차수열이 하나 더 생긴다는 의미이다.  하지만 +1은 나중에 해주고, ㅇ위에서 처럼 (길이가 3인 등차수열 개수)들의 합을 최종 답ans에 더해주고, 길이가 4인 등차수열의 개수로 저장한다.

현재 길이가 2인 등차수열의 개수를 인정했기 때문에 길이가 2인 등차수열의 개수는 사실 길이가 3인 등차수열의 개수를 뜻하게 되고, 길이가 3인 등차수열의 개수는 (길이가 2인 등차수열의 개수+1한 값들의 합이기 때문에) 길이가 4인 등차수열의 개수를 가리키게 된다... 즉, 이렇게 계속 길이가 n인 등차수열의 개수를 구해 나가되, 실제로는 길이가 n+1인 등차수열의 개수를 의미하므로 최종답 ans에는 길이가 2인 등차수열의 개수부터 n-1인 등차수열의 개수만 저장하면 되는 것이다.

(참고로 이해를 위해 등차수열의 길이를 언급했지만 사실 등차수열의 길이를 이용해서 푸는 것은 아님.)

여기서 중요한 것은 같은 등차수열이여도 인덱스 구성이 다르면 다른 것으로 쳐서 count해줘야 하고 길이가 3이상인 등차수열부터 인정이 되므로 길이가 2인 등차수열의 개수는 0인데, 이렇게 할 경우 인덱스 구성이 다른 것을 카운트하지 못하게 되는 문제가 있었고, 그렇다고 길이가 2인 등차수열의 개수를 count해 버리면 나중에 답을 구할 때, 길이가 2인 것을 어떻게 구별해서 제거할 것인가 하는 문제가 있었는데,
길이가 2인 등차수열의 개수를 count하고 원래 구하는 방식대로 구해나가되, 길이가 2인 등차수열의 개수는 (길이가 2인 그 수열들을 포함하는) 길이가 3인 등차수열의 개수와 같고, 길이가 n인 등차수열의 개수는 길이가 n인 등차수열을 구하기 위해 사용되는 길이가 n-1인 등차수열의 개수의 합이라는 것을 이용해서 결국 길이가 2인 등차수열의 개수부터 길이가 n-1인 등차수열의 개수만 답에 포함시켜 정답을 구할 수 있다.

좀 감격스럽다. 정말 하루 종일 이것만 생각한 것도 아니고 이것 때문에 아무것도 못했다고 해야되나 물론 내가 노력이 부족했지만... 그래도 끈기있게 붙들고 있었던 보람이 있는 것 같다. 비록 내가 생각을 못했지만 남의 코드를 이해했고, 새로운 접근 방식을 깨닫게 되었다. 난 무조건 길이가 n인 경우를 구해야 한다고 생각했는데... 길이가 2인 경우는 경우의 수를 무조건 0으로 둬야 한다고 생각했는데... 발상의 전환인가... 원리를 파고든 것인가.. 여튼 멋지다.

그런데 저렇게 구현해도 틀린다. 아무래도 map이 느려서 그런 것 같다. 이제 unordered_map을 공부할 차례다.... 음 어렵다.
일단 unordered_map에 대해 알지는 못하지만 unordered_map을 사용해서 (사실 사용하는 것도 어려웠다, 그리고 C++11에서 사용 가능) 구현했다.

그리고 깨달은 것이 이 문제에서 map의 기능은 2차원 배열에 대해서 필요한 것이 아니라 1차원 배열에만 필요하다. 그렇기 때문에 이 것을 이진탐색으로 구현해 봐도 될 것 같다... 막상 해보려고 하니까 이진탐색으로 하려면 정렬이 되어있어야 하는데.. 쉽지 않다. 그래서 map이 이진 트리를 사용하나보다...

BOJ 5012 불만 정렬

< 출처 >
http://xoding.tistory.com/158
http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220806808977

일단 구하고자 하는 세 수에서 가운데 수를 잡고, 가운데 수를 지정한 후 그 수보다 왼쪽에 있으면서 더 큰 수의 개수 오른쪽에 있으면서 더 큰 수의 개수를 곱해나가면서 답을 구할 수 있다고 한다.... 생각도 못했는데 대단하다...

그런데 여기서 어떻게 세그먼트 트리나 팬윅트리를 이용할 것이냐?

풀이와 코드를 봤지만 아직도 이해가 완벽히 되지 않았다.

일단 가운데 수를 앞에서부터 주어진 위치의 순서대로 보면서 나가보자.
가운데 수를 기준으로 왼쪽의 그 수보다 큰 수, 오른쪽의 그 수보다 작은 수가 각각 몇 개 있는지 알고 싶다. 세그먼트 트리나 팬윅트리에 무엇을 저장할 거냐면 처음에 입력받은 수의 개수를 저장할 것이다. 즉, 트리의 범위는 1에서 n까지가 되는 것이다.
그렇게 입력받은 수의 개수를 저장해두고 query(x, y)를 하면 주어진 수열에서 x이상 y이하의 수의 개수를 얻을 수 있는 것이다.

자, 왼쪽, 오른쪽을 각각 담당하는 트리 두 개를 만들자.  처음에는 일단 오른쪽 수들에 해당하는 트리를 입력받으면서 입력받은 수의 개수를 저장해 놓는다. 그리고 순서대로 볼 때, 왼쪽에 있는 자신보다 큰 수의 개수를 알고싶다. 맨 처음 수는 일단 왼쪽에 아무것도 없을 것이다. 그리고 실제로 왼쪽을 담당하는 트리에는 처음에는 아무것도 들어가있지 않다. 그럼 오른쪽을 보자. 오른쪽에 있는 수 중 자신보다 작은 수의 개수는 어떻게 구할까? 아까 만들어 놓은 오른쪽 담당 트리에서 현재 위치한 가운데 수보다 작은 수들의 합을 구하면 된다.
즉, query(1, cur-1)하면 될 것이다. 그러면 자신보다 오른쪽에 있으면서 작은 수들의 개수를 구할 수 있다.

그리고 다음이 중요하다. 이제 다음 가운데 수 후보를 볼텐데 넘어가기 전에 방금 가운데 수로 가정했던 수는 더 이상 다음 가운데 수보다 오른쪽에 있지 않기 때문에 오른쪽을 담당하는 트리에서 그 수에 해당하는 개수를 -1해서 지워버린다. 그리고 이제 다음 가운데 수 기준으로 왼쪽에 그 수가 들어가기 때문에 왼쪽을 담당하는 트리에서 그 수에 해당하는 개수를 +1해준다!

그렇다. 바로 트리 두 개로 왼쪽, 오른쪽에서 각각 어떤 수보다 크고 작은 수의 개수를 O(logN)만에 계산하되, 주어진 수들을 순서대로 보면서 더이상 어떤 수 기준으로 오른쪽에 있지 않은 수, 이제 왼쪽에 있게되는 수를 업데이트 해주면서 어떤 가운데 수를 기준으로 해서 원하는 값을 구할 수 있는 것이다.


그리고 트리를 하나만 사용하려면 왼쪽, 오른쪽의 개수를 따로 따로 구해서 배열에 넣어놓고 계산은 나중에 해주면 된다. 따로 구할 때 좋은 방법이 있는데, 트리에 값을 넣어놓지 말고 왼쪽의 경우 앞에서부터 보면서 집어넣고, 오른쪽의 경우 뒤에서부터 보면서 집어넣으면 된다. 아직 트리에 들어가지 않은 값들은 가운데 값보다 크다고 해도 왼쪽에 있는 값이 아니거나 작다고해도 오른쪽에 있는 값이 아니므로, 트리에 넣어주면서 즉 여태까지 살펴본 값들 중에서만 자신보다 작거나 큰 값의 개수를 세주면 된다!

그리고 이 문제는 +1, -1을 하기 때문에 Fenwick Tree가 편해보이는데, Segement Tree를 쓰더라도 조금 변형을 하면 된다. 여태까지 update(index, newValue...)에서 index에 해당하는 곳(leaf node)을 newValue로 교체했는데, index에 해당하는 leaf node에 +1, -1을 해주고 올라가면서 상위 노드들을 업데이트 해주면 되는 것이다. 간단한 것인데도 나는 블로그를 보고 알았다. 생각도 못했었다. 확실히 내가 아직도 세그먼트 트리에 대한 이해와, 응용력이 부족하다는 것을 느낀다.

< 출처 >
http://xoding.tistory.com/158
http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220806808977

BOJ 1275 커피숍

일반적인 세그먼트 트리 문제이길래, 세그먼트 트리를 구현하고 당연히 맞을 줄 알았는데 틀렸다. 문제에서 입력은 int형 범위랬지만 구간 합은 long long이 될 수 있을테니 long long을 사용했는데도... 그래서 다른 분의 블로그를 찾아봤는데, x번째에서 수에서 y번째 수까지의 합을 구하는 것에서 x<=y가 아닐 수도 있다....고 한다.

예전에 처음 세그먼트 트리를 풀고 다른 분의 코드에서 x<=y가 아닌 경우를 가정해서 구현된 것을 보고 나도 주의해야지 생각했던 것인데...
x>y인 경우 swap을 해서 냈는데, 또 WA를 받았다. 원인을 보니... swap함수를 만들 때, parameter를 포인터나 참조자를 쓰지않고 그냥 복사해서 넘기는 식으로 해버렸다...

결국 AC를 받았다.

FenwickTree로도 풀어봐야겠다.
오히려 FenwickTree로 할 때 더 고생했는데... 여러가지 함정이 있겠지만 가장 찾기 힘든 함정에 대해 써보겠다.
FenwickTree의 경우 point update를 할 때, 해당하는 숫자를 바꿔주는 것이 아니라 원래 숫자와의 차이만큼 더해주는 식으로 하는데, 입력으로 int형 정수가 주어져도 양의 정수와 음의 정수로 주어질 경우 그 차이값이 int형 범위를 넘을 수 있다! 그렇기 때문에 그 부분을 long long으로 처리해 줘야 한다.

물론 이런 문제들은 모든 변수를 long long으로 처리하면 일어나진 않겠지만... 주의해야할 점이다.

BOJ 13907 세금 - 벨만 포드, 다익스트라 공부하고 다시 풀어보기...

여러 도시들과 그 도시들을 잇는 도로와 통행료가 주어진다. 그리고 출발점 도시A와 목적지 도시B가 주어지는데 이 때, A에서 B로 가는 길의 통행료의 합이 가장 작은 경로를 구해야 한다. 정확히는 최소의 통행료를 구해야 하는데, 이럴 경우 다익스트라를 이용하면 쉽지만, 이 문제에서는 매 단계별로 모든 도로의 통행료가 입력에 각 단계별로 주어진 만큼 인상된다. 이 때, 각 단계별 A에서 B로 가는데 드는 통행료의 최소값을 구하는 문제이다.

매 단계별로 다익스트라를 다 돌려보는 것이 가장 쉬워보이지만 그럴 경우 TLE를 받게 된다. 어떻게 해야할까? 여러 방법이 있겠지만 난 다익스트라를 이용해서 풀어봤다.

이 문제에서 핵심은 A에서 B까지 몇 개의 길을 거쳐 갔는지이다. 각 단계에서 세금을 인상할 때, 모든 도로의 통행료가 인상되기 때문에 A에서 B까지 거쳐간 길이 많을 수록 전체 통행료가 많이 올라가게 된다. 즉, 몇 단계에 걸친 세금 인상마다 통행료가 최소인 경로가 달라질 수 있는 것이다. 

좀 더 생각해보면 세금이 인상됨에 따라 현재 최소인 경로보다 거쳐간 길의 개수가 적은 경로들이 최소가 될 가능성이 있는 경로들이다. 거쳐간 길이 많은 경로들은 그럴 가능성이 없다. 

그런데 여기서 더 이상 나아가진 못하고 일단은 다익스트라를 이용하되, 일반적인 다익스트라 알고리즘에서는 한 정점에서 다른 정점까지의 최단 거리를 구했다면, 이 문제를 풀 때는 한 정점에서 다른 정점까지 x개의 길을 거쳐가는 최단 거리를 구하는 식으로 생각해 봤다.

d[node] = src에서 node까지의 최단 거리... 였다면,

d[node][x] = src에서 node까지 x개의 길을 거쳐서 가는 최단 거리로 놓는다.

d[node][x] > d[node][x-1] + cost 이면 d[node][x]를 업데이트 해주는 식으로 다익스트라를 구현한다. 근데 도시의 개수가 1000개 그 도시들을 잇는 길의 개수가 30만개라서 처음에 

d[1001][300000]로 잡았다가 메모리 초과가 났는데, 생각해보니 저렇게 잡을 필요가 없다.

d[1001][1000]이면 된다. 왜냐하면 최단 경로는 최대 node-1개로 이루어질 수밖에 없기 때문이다. node-1개의 경로보다 많은 경로를 거치면 한 점을 두 번 이상 방문하게 되므로 불필요한 방문을 한 것이고 최단 경로가 될 수 없으므로 고려할 필요가 없다.

그리고 저렇게 구현하고도 또 틀렸는데, 내가 방문한 경로가 node-1을 넘어가는 경우도 그냥 나둬서 그런 것이었다. 중간에 node-1개를 방문했으면 그 node까지의 최단 거리는 더 이상 구할 필요가 없다.

그래서 결국 AC를 받았는데, 맞은 사람 목록에서 다른 사람들의 코드와 시간이 10배 정도 차이가 난다. Baekjoon Online judge게시판에 이 문제에 대한 풀이(서강대 대회 문제였다.)가 올라와 있다고 하니 보고 공부하고 다시 풀어봐야 겠다.

풀이를 봤는데 일단 접근은 비슷한 것 같은데 구현이 다익스트라가 아닌 벨만포드 비슷한 방식으로 한 것인데... 벨만포드를 까먹어서..(아..복습ㅠ) 왜 다익스트라보다 10배 정도나 빠른건지...제대로 이해하지는 못하고 다른 분들 코드도 보다가.. 다익스트라를 쓰신 것 같은데도 불구하고(게다가 자바로 구현하셨는데도...) 속도가 매우 빠른 분이 계셔서, 그 코드를 이해는 못했지만 다익스트라도 시간을 단축시킬 수 있다는 희망을 가지고 나도 내 코드에서 좀 더 시간을 단축시킬 방법을 고민해 봤다.

생각해보면 어떤 점 V까지의 최단 거리를 구할 때, V까지 n개의 길을 거쳐서 가는 최단 거리를 구했다고 치자. 근데 매번 세금이 오를 때마다 통행료가 길의 개수만큼 인상되기 때문에 V까지 같은 최단거리라면 길의 개수가 더 많은 경우는 볼 필요가 없다.

다익스트라 알고리즘에서 난 priority queue를 사용했기 때문에 최대한 pq에 들어가는 간선을 줄이면 시간과 메모리를 단축시킬 수 있을 것이다. 

V까지의 n개의 경로를 거쳐 간 최단 거리가 V까지의 n-1개 이하의 경로를 거쳐 간 최단 거리보다 같거나 혹은 크다면 더이상 V까지의 n개의 경로를 거쳐 간 경우와 그 경우에서 파생되는 경우는 볼 필요가 없어서 큐에 넣지 않았다. n-1개 이하의 경로를 거쳐간 최단 거리와 거기서 파생된 경우만 보면된다.

근데 n-1개 이하의 경로를 거쳐간 경우를 보기 위해서 for문을 n번 돌려주기 때문에(break을 넣긴 했지만) 오래 걸리지 않을까 걱정도 했지만... 제출해보니 시간이 무려 20배정도 단축됐다(메모리는 3배정도)... 내가 이 다익스트라에서 2차원 배열을 쓰는 경우의 시간 복잡도를 모르겠는 것도 있고 지금 다익스트라, 벨만포드등을 다시 공부해봐야 할 것 같아서 왜 이런 결과가 나왔는지 정확히 내 알고리즘의 개선이 얼마나 된건지 아니면 테스트 케이스가 약해서 그런건지.. 잘 모르겠다.  풀이는 dp로 이해하면 될 것이다.

일단 공부를 더 해보고 이 문제는 다시 풀어봐야 겠다.
-------------------------------------------------------------------------------------
풀이를 봤더니 dp였다.
d[n][r] = n번도시 까지 r개의 길을 거쳐 갈 수 있는 최단 거리
d[n][r] = min(d[pre][r-1], pre는 n번도시와 연결된 도시들) 혹은
d[here][r]을 이용해서 d[there][r+1]을 구할 수 있을 것이다.
d[src][0]=0으로 두고 배열을 채워 나가면 최단 거리가 구해질 것이다.

이렇게 dp로 구현하면서 어떻게 시간을 단축시킬까 고민하다가
위에서 이용한 원리를 또 사용해봤다.
d[n][r]배열을 구하는 곳에는 적용 못할 것 같아서 마지막에 세금을 올리는 단계별로 최소값을 구해서 출력하는 과정에서 적용했는데, 세금을 올릴 수록, 답이 되는 최소경로는 반드시 지나는 길의 개수가 같거나 작아질 수 밖에 없다. 세금이 지나는 길의 개수에 비례해서 늘어나기 때문에 세금을 부과하는 단계가 높아질수록 최소경로는 이전과 지나는 길의 개수가 같거나 작을 수밖에 없는 것이다.
이 사실을 이용해서 최소 경로를 구할 때, 지나는 길의 개수를 저장해두고, 최소 경로를 구할 때마다 이전 최소 경로의 길의 개수이하인 경우만 보는 식으로 구현했다.  이전 최소 경로의 길의 개수보다 큰 경우는 절대 최소 경로가 될 수 없다.

그리고 이것을 이전에 다익스트라로 구현한 코드에 추가했더니 또 시간이 단축되었다.

생각하는데 도움이 된 질문 게시판 답변 : https://www.acmicpc.net/board/view/10855