7569. 토마토

https://www.acmicpc.net/problem/7569

1. 접근

http://js1jj2sk3.tistory.com/59 이랑 똑같다.

맵만 삼차원으로 바뀌었음.

2. 풀이

방향만 6방향으로 늘려주면 해결

3. 코드

1. 접근

익은 토마토는 주변의 익지 않은 토마토를 전염시켜 익게 만든다.

주변이란 위, 아래, 왼쪽, 오른쪽의 사방향을 말하며, 익은 토마토의 전파는 하루가 걸린다.

맵의 모든 토마토를 익게 만드려면 몇 일이 걸릴까?

실제로 익어가는 과정을 시뮬레이션해보면 알 수 있다.

다만 익은 토마토를 기록해주고 전파되는 과정을 구현하고, 동시에 모든 토마토가 익었는지 확인하는 구현도 필요한데,

마침 BFS는 매우 유사한 구조를 띄고 있다.

익은 토마토를 기점으로 전파하는 방법은, 노드를 방문해나가는 과정과 비슷하며,

익은 토마토를 다시는 확인할 필요가 없는 구현은, visit을 체크하면서 다시 방문하지 않는 과정과 같기 때문이다.

2. 풀이

먼저 0일차의 익은 토마토의 좌표들을 큐에 저장한다. 1일차로 나아갈려면 어떻게 해야할까?

BFS의 특성상 진행할 수 있으면 다시 큐에 들어가야 하므로, 일자를 기록할려면 0일차의 토마토 갯수만큼 큐질을 해야한다.

따라서 큐의 사이즈만큼(X일차에 새롭게 익은 토마토 갯수)만 큐질을 하면 일자를 기억하면서도 큐질을 할 수 있다.

또한 0인 토마토를 1로 익게 만들고 나서 0인 토마토가 더이상 없으면 탈출조건으로 잡을 수 있다.

이렇게 하면 온갖 큐질 이후에도 0인 토마토가 남는 상황도 체크할 수 있다.

3. 코드

사실 visit 배열을 따로 쓰지 않아도 BFS질을 할 수 있긴 하다.

10989. 수 정렬하기 3

10
5
2
3
1
4
2
3
5
1
7

1
1
2
2
3
3
4
5
5
7

1. 카운팅 정렬 소개

이제 소개할 카운팅 정렬은 매애우 간단하고 빠른 알고리즘이다. 간단하고 빠른 만큼 제한적이고, 메모리를 많이 소비한다.

쉬운 버블 / 삽입 정렬은 O(n ^ 2) 이었고, 병합 / 힙 정렬은 O(n * log n) 이었다.

카운팅 정렬은 O(n) 으로 선형시간이다!

카운팅 정렬은 말 그대로 숫자가 몇 번이나 나오는지 세는 알고리즘이다. 소개하기도 뭐한 매우 간단한 알고리즘인데,

필요한 배열은 숫자가 몇 번 나오는지 기록할 배열이다. 위의 문제에선 등장할 수가 10,000 보다 작거나 같은 자연수로 제한되어 있기 때문에 만칸의 배열만 준비하면 된다.

따라서 카운팅 정렬은 정렬할 원소들의 범위를 알고 있는 상황에서만 쓸 수 있다.

또한 그 범위는 메모리에 올릴 수 있을 정도여야한다.

[1, 100, 2, 1, 50] 이라면 백 칸짜리 배열이 필요하겠다.

이제 정렬한 결과를 출력하는데는 두 가지 방법이 있다.

첫째로는 걍 백 칸짜리 배열을 앞에서 부터 보면서 기록된 갯수만큼 출력하는 것이다.

인덱스 1을 보고 기록된 숫자가 2 이므로 1을 두 번 출력한다.

이 경우에 메모리 사용량은 숫자 등장 범위에 영향을 받는다.

두번째 방법으로는 백 칸짜리 기록용 배열을 누적합으로 바꿔주는 것이다.

-> 누적합[1] = 2 / 누적합[2] = 3 / ... / 누적합[50] = 4 / ... / 누적합[100] = 5

이제 기록용 배열은 해당 숫자가 정렬된 배열의 어떤 범위에 존재해야 하는지 나타낸다.

즉, 누적합[1] = 2 이므로, 배열의 앞에서 부터 두칸을 차지한다는 뜻이고,

바로 뒤의 누적합[2]는 3이니까 세번째 칸을 차지한다는 뜻이다.

누적합[3] [4] ... [49] 는 연속해서 3이므로 정렬결과용 배열에 들어가지 않는다.

또한 이 방법은 입력순서를 기억해야한다. 마지막 입력은 50 이었고 누적합[50] = 4 였으므로,

50은 정렬용 배열 네번째 칸에 들어간다. 누적합[50] = 3으로 줄어든다.

50의 전 입력은 1이었다. 누적합[1] = 2 이므로 1은 정렬용 배열 두번째 칸에 들어간다. 누적합[1] = 1로 줄어든다.

이 방법은 따라서 입력의 갯수에 비례해서 연산을 하고, 메모리도 차지한다.

두 방법중에 알맞은 방법을 쓰기로 하자.

위의 문제에선 숫자 등장범위가 10,000 이고 입력은 10,000,000 개 이니까 첫번째 방법을 쓰기로 했다.

2. 코드

3. 시간 복잡도

일단 입력이 n개 들어오므로 입력엔 O(n)이 걸린다. 출력도 결국엔 n개를 출력해야 하므로 O(n)이다.

2751. 수 정렬하기 2

https://www.acmicpc.net/problem/2751

5
5
4
3
2
1

1
2
3
4
5

1. 힙 정렬 heap sort 소개

O(n * log n)의 시간복잡도를 가지는 또 다른 정렬 알고리즘을 알아보자 

힙 정렬은 말 그래도 힙 자료구조를 사용한 정렬방법이다.

따라서 이해하기 위해선 힙이 무엇인지부터 알아야 한다!

1-1) 힙 자료구조 소개

우선 힙은 완전이진트리다. 

이진트리라 함은 한 노드가 최대 두 개의 자식노드를 가진다는 뜻이고,

완전이진트리라 함은 마지막 level = depth 를 제외하고 모든 레벨은 노드가 가득 차있으며, 마지막 레벨은 노드가 왼쪽부터 채워져 있다는 뜻이다.

힙의 강점은 부모-자식 간에 대소관계가 전부 적용되어 있다는 것이다. 단 형제들 끼리는 적용하지 않는다.

(최대힙이라면) 따라서 루트노드는 가장 큰 노드가 될 것이다.

따라서 이러한 힙(최대 힙)을 유지한다면 O(1)에 가장 큰 수를 찾을 수 있다.

우선순위 큐도 비슷한 자료구조로 구현되어 있다고 한다.

1-2) 힙 자료구조 구성하기

힙은 트리로 되어있지만, 완전이진트리라는 점에서 배열로 구현할 수 있다.

루트노드를 인덱스 0으로 잡을시, 부모 노드의 인덱스가 x라면, 왼쪽 자식의 인덱스는 (x * 2 + 1),

오른쪽 자식의 인덱스는 (x * 2 + 2) 이다.

루트노드를 인덱스 1으로 잡을시, 부모 노드의 인덱스가 x라면, 왼쪽 자식의 인덱스는 x * 2, 

오른쪽 자식의 인덱스는 (x * 2 + 1) 이다.

이제 전체 배열을 힙으로 만들어 보자!

힙으로 만드는데는 부모노드를 조지는 방법이 효과적이다.

간단히 노드 세 개의 이진트리를 생각해보면,

루트 노드가 3이고, 두 자식 노드가 모두 3보다 크다면 어찌되었건 부모 노드를 아무 자식과 스왑해주면 끝이다.

그래서 작은 부분 부분 힙을 만들어주면서 확장시키는 방법을 쓴다.

코드로 보면 이해가 빠르당

x를 부모 노드로 잡고 힙이 될 조건(부모가 제일 큼)을 만족할 때 까지 밑으로 조져버린다.

함수를 배열 맨 뒤에서 부터 호출해주면 되는데,

시간을 절약하기 위해선 리프 노드에 대해선 호출할 필요가 없다는 점을 기억하자.

1-3) 힙 정렬하기

이제 힙을 완성했으니 정렬에 써먹어 보자.

힙의 장점 : 최대값을 O(1)에 알 수 있다 / 를 활용하는 것이다.

오름차순이라면 배열의 최대값은 배열 맨 뒤에 있어야 한다. O(1)에 알 수 있다. 힙에서 베껴온다.

그럼 그 다음으로 큰 수는 어떻게 알 수 있을까? 

일단 다음으로 큰 수는 루트(부모)의 두 자식 중에 한 놈이다.

하지만 우리의 목표는 계속 힙 구조를 유지하면서 장점을 써먹는 것이므로, 루트를 잃어버린 힙을 재구성해야 한다.

재구성은 간단하다. 위에서 했던 down_heap()을 활용한다.

루트를 힙의 누군가로 새롭게 대체하고 밑으로 조져버리면, 루트의 두 자식 중에 큰 놈이 위로 올라올 것이고, 대체자는 본연의 자리를 찾아갈 것이므로 힙이 새롭게 재구성되는 것이다.

루트를 새로 채울 놈은 누구를 써야 하는가? 만만한건 제일 마지막에 있는 리프 노드다.

그림으로 확인해보자.

2. 코드

3. 시간복잡도

힙 정렬 알고리즘은 간단히 쓰면 다음의 단계를 거친다.

1) 주어진 배열로 힙을 만든다.

2) 루트노드를 새로운 배열로 옮기고, 힙의 말단으로 루트를 대체한뒤, 다운힙 시킨다.

1번의 과정은 얼마나 걸릴까?

우선 힙을 만드는데 down_heap을 썼던 점을 기억하자.

down_heap은 결국엔 이진트리의 높이만큼 수행될 것이다 -> O(log n)

또한 배열의 맨 뒤 부터 밑으로 조져버린다는 점에 의해 -> O(n * log n) 안에 수행된다.

2번 과정도 동일하다. O(1)에 루트노드에 접근할 수 있으며, 다운 힙은 O(log n) 안에 수행된다. 이를 n개에 대해 연산한다.

따라서 O(n * log n) 임을 알 수 있다.

2751. 수 정렬하기 2

https://www.acmicpc.net/problem/2751

5
5
4
3
2
1

1
2
3
4
5

1. 병합 정렬 merge sort 소개

앞선 두 개의 정렬 알고리즘은 어찌됐건 O(n ^ 2)의 시간복잡도를 가진다.

위의 문제를 보면 최악의 경우 백만 칸의 배열을 정렬해야 한다.

백만의 제곱으로는 시간 제한내에 들어오지 못한다.

그러면 더 빠른 알고리즘을 알아햐 하니까, 병합 정렬에 대해 알아보려고 한다.

우선 병합 정렬은 분할 정복이다. 즉 문제를 쪼개어서 부분 문제로 만들어 해결하자는 뜻으로, 결국 재귀적인 패러다임이다.

때문에 하위 문제는 상위 문제보다 적용 범위가 작아야 하고, 범위가 작아지는 한계인 탈출지점이 있어야 한다.

분할 정복은 다음 세 부분으로 나눌 수 있다.

1) 분할 : 원래의 문제를 분할하여 같은 문제 유형의 더 작은 하위 문제들로 나눈다.

2) 정복 : 하위 문제들을 재귀적으로 해결해야 한다. 충분히 하위 문제가 작아졌다면 탈출해야 한다.

3) 합치기 : 하위 문제들의 답을 합쳐 원래 문제를 해결한다.

도식화 하자면 다음과 같다.

이제 병합 정렬을 분할 정복해보자. 하위 문제를 잘 정의해야 한다.

당연히 원래의 문제는 수열을 정렬하는 것이다. 하위 문제는 수열의 일부분만 정렬하는 문제라고 정의하자.

폰 노이만은 병합 정렬을 만들 때 다음의 단계를 거치라고 했다.

1) 분할 : 수열을 반으로 쪼갠다.  [14, 7, 3, 12, 9, 11, 6, 2] ->  [14, 7, 3, 12] /  [9, 11, 6, 2]

2) 정복 : 쪼개진 수열 각각에 대해 정렬한다. [3, 7, 12, 14] /  [2, 6, 9, 11]

3) 결합 : 두 수열을 합쳐서 정렬한다 [2, 3, 6, 7, 9, 11, 12, 14]

하위 배열 [14, 7, 3, 12]은 어떻게 정렬할까? 마찬가지로 분할-정복-결합을 거쳐 [3, 7, 12, 14] 로 만든다.

다음은 위의 예시가 어떻게 재귀적으로 전개되는지 과정을 보여준다.

2. 코드

아마 병합단계를 구성하는게 가장 어려웠을 것이다.

단순히 두 배열을 합치고 지금까지 배운 삽입-정렬이나 거품-정렬을 쓸 수도 있지만

그리한다면 오히려 더 느린 알고리즘이 되어버린다.

이를 선형시간에 해결할 아이디어는, 우리가 문제를 재귀적으로 풀고 있었다는 점에서 떠올릴 수 있다.

우리가 합쳐서 정렬할 두 부분 배열의 특징은 무엇인가? 바로 이미 재귀적으로 정렬되어버린 배열이라는 점이다.

따라서 다음과 같은 방법을 쓸 수 있다.

4칸 부분 배열 두 개를 합쳐 8칸 짜리 배열을 만들어야 한다고 해보자.

첫칸에는 어떤 숫자가 와야 하는가? 8개 숫자 중에 가장 작은 수이다.(오름차순)

고맙게도 두 부분 배열의 맨 앞은 가장 작은 숫자의 두 후보이다. 따라서 두 배열의 맨 앞의 숫자 중에 작은 수를 가져다 쓰면 된다.

둘째 칸에는 어떤 숫자가 와야 하는가? 두번째로 작은 숫자이다.

후보는 두 배열의 맨 앞 숫자이다.(인덱스로는 1 / 0)이다. 두 숫자중 작은 수를 가져다 쓴다.

....

그래서 n칸 짜리 임시배열을 만들고, 채우고, 다시 원본 배열에 복사해주는 편이 편하다.

원본 배열만 써서 이를 구현하면(in-place) 번거롭고, 오래걸린다.

3. 시간 복잡도

결론적으로 병합-정렬의 시간복잡도는 O(n * log n)이다. 백만 개가 주어진다면, O(백만 * 6)이다.

어떻게 차수는 줄어들 수 있었을까? 재귀적으로 분석해보자.

결국 최종적으로 완성되는 배열은 두 부분 배열(이미 정렬된)을 합치면서 완성된다. 위에서 합치는 방법이 선형시간임을 보였으므로,

합치는데는 O(n)이다.

그러면 정렬된 두 부분배열을 만드는데는 얼마나 걸렸을까? 각각의 크기는 n/2 이므로 O(2 * (n / 2)) = O(n) 만큼 걸렸다.

그림으로 알아보자.

그림을 통해 알 수 있는 사실은 O(n)은 트리의 높이만큼 수행된다는 것이다.

트리의 높이는 얼마나 되는가? log n 이다. 따라서 시간복잡도는 O(n * log n)이다.

또한 생각할 점은 원래의 배열이 어찌되었건 간에 쪼개는 상황은 반복된다는 것이다.

따라서 최선의 경우(이미 정렬되어 있어도)에도 시간복잡도는 O(n * log n) 이다.

2750. 수 정렬하기

5
5
2
3
4
1

1
2
3
4
5

1. 거품 정렬 소개

삽입 정렬 다음으로 간단한 정렬 알고리즘을 소개하고자 한다.

마찬가지로 인간의 정렬 방법과 유사한 알고리즘이다. 삽입 정렬에선 가지고 있는 숫자 타일을 하나 내려놓고, 정렬하고 했다면,

이번에는 가지고 있는 숫자 타일 중 가장 큰 수 부터 내려놓는 방법이다.

그러면 가장 큰 수는 어떻게 찾을까? 당연히 전체를 다 뒤져야 한다.

여러 방법이 있겠지만, 거품 정렬에선 이름 처럼 거품이 떠오르는 듯한 방법을 쓴다.

1) 맨 앞의 두 인자를 비교해서(인덱스 0과 1), 올바른 순서면 바꾸지 않고, 아니라면 서로 바꾼다. (swap)

2) 이번엔 다음 두 인자를(인덱스 1, 2) 마찬가지로 비교하고 스왑한다.

3) 배열의 마지막 두 인자 까지 2)를 수행한다.

다 수행했으면 배열의 상태는 어떠할까? 중간 인자들의 상태는 뒤죽박죽일지 몰라도 가장 마지막 숫자는 올바른 위치에 있다.

오름차순으로 정렬하기로 했다면, 배열 중 가장 큰수가 가장 맨 마지막에 있게 되는 것이다.

이제 제대로 박힌 마지막 인자를 제외하고 다시 처음부터 과정을 반복하면 된다.

그러면 뒤에서 부터 올바른 위치로 인자들이 채워지는 것이다.

애니메이션으로 확인해보자.

뒤에서 부터 한 점씩 채워지는 과정을 눈으로 확인할 수 있다.

2. 코드

3. 시간 복잡도

삽입 정렬과의 차별점은, 삽입 정렬이 for문 안이 while문으로 되어있다면, 거품 정렬은 for문으로 되어있다는 점이다.

따라서 삽입 정렬은 운이 좋다면 while문이 별로 돌지 않고 끝날 수 있지만,

거품 정렬은 그런거 없고 무조건 for문을 다 돌아야 한다.

또한 최악의 경우 마찬가지로 이중for문으로 인해 시간복잡도는 O(n ^ 2)이다.

2750. 수 정렬하기

5
5
2
3
4
1

1
2
3
4
5

1. 삽입정렬 소개

인간은 정렬을 어떻게 하는가? 누군가에게 숫자 타일을 여러개 주고 오름차순으로 바닥에 정렬하라고 한다면,

아마 다음과 같은 과정으로 정렬할 것이다.

{5, 3, 4, 1, 2}

1) 일단 헷갈리니까 하나를 내려놓는다.

-> {5}

2) 이제 다음 타일을 내려놓아야 하는데, 들고 있는게 내려놓은 타일보다 작다면 앞에 놓고, 아니면 뒤에 놓을 것이다.

즉 적당한 위치에 놓을 것이다.

-> {3, 5}

3) 2의 과정을 반복한다.

-> {3, 4, 5} -> {1, 3, 4, 5} -> {1, 2, 3, 4, 5}

삽입정렬은 우리의 정렬방법과 닮았다.

배열을 앞에서 부터 정렬하는데, 이미 정렬된 부분과 비교하여 현재 보고 있는 요소를 알맞은 부분에 삽입하는 정렬이다.

그러면 알맞은 부분에 삽입은 어떻게 해야할까?

현재 보고있는 부분을 제외하고 앞의 부분은 이미 정렬되어 있음을 기억해야 한다.

따라서 한 칸씩 돌아가는데, 맨 처음으로 돌아가거나 자신보다 작은 원소를 찾으면 그만 돌아가야 한다.

{1, 2, 4, 5} 까지 정렬했고 이제 3을 삽입하려고 할 때, 2를 보고 그만 돌아가는 것이다. -> {1, 2, 3, 4, 5}

돌아가는 중에는 3보다 큰 숫자라면 뒤로 한 칸씩 미뤄줘야 한다. 그래야 3이 들어갈 자리가 생긴다.

따라서 3의 현재 인덱스(4)와 숫자 3을 기억해야 한다. 5가 바로 뒤로 밀려오기 때문이다.

3보다 작은 첫 숫자 2(인덱스 : 1)를 발견했으면 이제 바로 뒷 칸(인덱스 : 2)에 삽입하면 끝이다.

gif로 확인해보자.

오른쪽으로 한 요소씩 진행하면서 계속 정렬하고 정렬하는 과정이 잘 보인다. 

2. 코드

3. 시간 복잡도

매번 정렬한다는 부분 알고리즘 때문에 딱 봐도 느린 알고리즘이다. 

결국 내림차순으로 되어있는 수열을 정렬한다면 (최악의 경우)

n + (n - 1) + (n - 2) + ... = n * (n - 1) / 2 번 걸릴 것이다.

따라서 O(n ^ 2) 의 시간복잡도를 가진다.

2342. Dance Dance Revolution

1 2 2 4 0

8

1. 접근

발의 위치가 5가지 혹은 4가지로 좁힐 수 있으니 뭔가 그리디 하게 풀 수 있을까 생각이 든다.

하지만 빡대가리로는 직관적인 그리디 방법이 떠오르지 않으므로 만만한 다이나믹 프로그래밍으로 완전탐색 해보자.

2. 풀이

항상 다이나믹 프로그래밍으로 풀 땐 dp배열을 잘 정의해야한다.

어떻게 정의하느냐에 따라 시간복잡도가 달라지고 시간제한에 걸릴지 말지 판가름 할 수 있기 때문이다.

두 발로 와리가리 하는걸 보니 왠지 경찰차 문제 http://js1jj2sk3.tistory.com/52 가 떠오르긴한다.

당시 dp배열은 dp[경찰차 1이 마지막으로 처리한 사건 번호][경찰차 2가 마지막으로 처리한 사건 번호]로 정의했었다.

사건은 천개가 맥시멈이니까 백만 안으로 들어오는 dp배열이 가능했었다.

이 방법으로 이 문제도 조질 수 있을까?

ddr 노트가 십만가 들어온다니까 불행히도 불가능하다.

그래서 내 생각으로는 일단 몇번째 노트 짼지는 기억해야 하니까 십만칸은 기본적으로 필요하다.

또한 직관적으로 왼발 오른발의 상태를 나타내야하니 5 * 5 = 25 칸도 필요하다.

그래서 걍 25 * 십만칸으로 조지기로 하자. 이래버리면 20 MB 정도 써야한다 ㅜㅜ

(분명히 더 나은 방법이 있다. 맞은사람들을 보면 1MB 쓴 사람도 있다.)

그래서 dp[왼발 위치][오른발 위치][다음에 밟을 노트가 몇번째] 로 정의하고 나면

함수는 func(int l, int r, int i) = 현재 상태가 이러저러 할 때 앞으로 힘을 얼마나 더 써야하는지 최소량으로 정의된다.

함수의 기저사례는 i가 끝까지 가버려서 게임을 다해버린 경우다.

아니라면 두 발의 상태에 따라 함수가 다르게 확장된다.

먼저 두 발이 중앙에 있었다면, 다음 노트에 따라 왼발을 옮기든지 오른발을 옮기든지 하면 된다.

따라서 두 경우를 구해보고 최소값을 리턴하자. 

하지만 잘 생각해보면, 무조건 왼발/오른발을 옮겨도 똑같은 결과다.

다음 경우는 다음 노트가 내 두발 중 하나랑 겹치는 경우다.

이 때는 발은 그대로고 힘을 1만큼 쓰기만 하면 된다.

마지막 경우는 완전 새로운 노트로, 왼발을 옮길지, 오른발을 옮길지 따져봐야 한다.

또한 발을 옮길 때 힘을 다르게 쓰므로 주의하자.

중앙에서 옮기면 2을, 반대편으로 가면 4를, 아니면 3만큼의 힘을 쓴댄다.

3. 코드

4. 후기

재귀질이니까 바텀업보다 메모리도 시간도 더 쓰긴한다. 코드를 좀 더 간결하게 써서 시간을 최대한 줄여보자.

2618. 경찰차

6
3
3 5
5 5
2 3

9
2
2
1

1. 접근

그리디로는 풀 수 없다. 당장 가까운 경찰차를 보낸다고 하면, 남은 문제는 방금 푼 문제의 조건과 달라지기 때문이다.

그러면 당연히 다이나믹 프로그래밍으로 다 해봐야 한다!

2. 풀이

배열을 어떻게 잡아야 시간안에 풀 수 있을까? 즉, 공통된 계산부분을 잘 만들어내야한다.

모든 경우을 빡대가리처럼 다 계산해버리면 2 ^ 1000 만큼 계산해야 한다.

그럼 무엇이 공통된 사건일까? 중요한건 당연히 현재 경찰차 두대의 위치다.

사건 순서대로 경찰차가 출동한 순서를 예를들어 1->1->2->1->1 이라 해보자. 어쨌건 다섯번 출동하고 나서의 경찰차 두대의 위치는 2->1->2->1->1 와 같다. 경찰차 1은 다섯번째 사건위치에 있을 것이며, 경찰차 2는 세번째 사건위치에 있을 것이다.

그러면 우리는 dp배열을 다음과 같이 정의할 수 있다. dp[x][y] = 현재 경찰차 위치가 x, y 일 때 남은 최소이동거리.

문제는 지금까지 몇번 출동했는지를 모른다는 점이다. 하지만 경찰차 위치는 {1,1} 아니면 {n,n} 아니면 사건위치 이므로, 간략히 0~n 까지의 번호가 부여된 위치로 대체할 수 있다. 동시에 지금까지 얼마나 사건을 처리했는지도 알 수 있다.

따라서 dp[x][y] = 현재 경찰차가 가장 최근에 처리한 사건이 x, y 일 때 남은 최소이동거리. 라고 정의한다.

max(x,y) = k 라면 지금까지 k번째 사건까지 출동했다는 이야기가 된다. 그러면 이제 k+1 사건에 대해 두 대를 출동시켜보고 최소인 경우로 리턴해주면 되겠다.

문제에서 요구하는 답은 추가적으로 사건마다 어떤 경찰차가 출동했는지도 출력해야 한다. 어떻게 알 수 있을까?

dp배열을 갱신하면서 값을 알 수 있는 방법도 분명있다. (하지만 내가 빡대가리라 따로 구하기로 한다.)

dp배열을 모두 갱신하고 나면, 각 칸마다의 정보를 이용해서 어떤 경찰차가 출동했는지 알 수 있다.

만약 dp[1][2] = 10 이고, 확장되는 두 가지 dp[1][3] = 7, dp[3][2] = 5 라면, 당연히 1번 차를 출동시켜 3번 사건을 맡게 했다는 뜻이다.

모든 경우에 대해 이미 계산이 끝났으므로, 사건 수만큼 재귀를 돌고 어떤 차가 출동했는지 알 수 있다.

3. 코드

2098. 외판원 순회

https://www.acmicpc.net/problem/2098

4
0 10 15 20
5  0  9 10
6 13  0 12
8  8  9  0

35

1. 접근

DP로 완전탐색 하자

2. 풀이

모든 방문경로를 dp 배열에 담으려면 dp를 어떻게 정의해야 할까?

일단 한 번 방문한 도시로는 돌아가지 않으니까(사이클 없슴) 마지막으로 방문한 도시로 경로를 일단 나눠볼 수 있다.

하지만 이것만으로는 부족하니까 지금까지 어떤 도시를 방문했는지를 기억해야 한다.

따라서 1->3->4->2 와 1->4->3->2 는 같은 dp칸에 담기겠지만, 두 경로 중 최소값이 dp에 담길 것이므로 문제에 적합하다.

dp[cur][stat] = 현재 내위치가 cur이고, 지금까지 stat의 도시들을 방문했을 때 최소값.

stat을 비트로 표현한다면 적당하다. 0이면 미방문이고, 1이면 방문했다.

예시의 경우 dp[2][000...1111]이 되겠다.

이제 dp를 채워줄 함수를 정의해보자.

func(int cur, int stat) = dp[cur][stat]을 계산해준다.

다음 지점을 방문할 때 계산은 어떻게 해야할까?

stat을 보고 해당비트가 0인 도시에 대해 함수를 콜하면 되겠다.

3. 코드

4. 후기

방문안한 지점중에 최소값을 찾는 부문에 무턱대고 int m = INT_MAX 을 써버렸더니 틀려버렸다..

생각해보니 포문을 돌고나도 여전히 INT_MAX라 리턴해버리면 다른데가서 cost가 더해져버리고 엉망이 되는 경우가 있었다.

빡대가리