바로가기

5번문제의 경우 gist에 올라가 있는 제 소스는 수정이 필요한 소스입니다.

5번 소스는 안보셔도 됩니다. 하지만 다른 사람이 동일 방법으로 250점을 맞았기 때문에 풀이법만 적겠습니다.

제 소스는 나중에 문제가 올라와서 제출이 가능해지면 수정하겠습니다.

풀이 방법

1. max는 항상 2^n 이 답이 됨이 자명하며, min의 경우 (n-1)/3이 되는 경우가 존재하기 때문에

완전 탐색을 통해 탐색을 하였습니다. 답이 될 가능성이 없는 가지들을 쳐내어 시간을 절약하였습니다.

2. 2차원 배열을 이용한 다이나믹 프로그래밍으로 풀었습니다. 저격수가 존재하여 발걸음에 대한 필터링이 필요하므로 추가로 1차원 배열을 하나 더 사용하였습니다.

DP[i][j] = 현재 나의 위치가 i 일 때, 이 i 위치를 j 칸 건너뛰어 도착한 경우

total[i] = i번째 위치를 도착할 수 있는 모든 경우의 수

맨 처음 아군 진영에서 몇 칸을 건너 뛰던 첫 발걸음을 떼는 경우의 수는 1가지이므로 total[0] = 1로 설정합니다.

1차원 for문을 통해, i 번째 위치의 DP[i][j]를 구할 때, 각 j의 경우의 수를 구하기 위해 2중 for문을 돌리면 nk^2으로 시간초과가 납니다.

따라서 i-j 번째 위치에서 i 번째로 올 때, 저격을 제외하는 경우의 수를 구하기 위해 DP[i][j] = total[i-j] - DP[i-j][j] 를 이용하여 구할 수 있습니다.

이 방법으로 구하면 nk가 되어 시간초과가 나지 않습니다.

3. 문제의 조건을 잘 읽어보면 결국 어느 한 정점의 차수는 항상 K개 이상을 유지해야 하며, 어느 정점이 감염되더라도 멀쩡한 나머지

정점의 개수가 L개 이상이 되어야 한다는 것입니다. 어렵게 생각할 필요없이, 주어진 간선 정보를 입력받아 1차원 배열에 차수를 추가합니다.

만약 입력이 1 3 이라면 node[1]++, node[3]++ 식으로 하면 됩니다. 또한 간선의 정보는 Edge[i][j] = Edge[j][i] = 1 로 저장할 수 있습니다.

그 다음 1번 차수부터 for문을 이용하여 위의 K, L 조건을 만족하지 않는지를 확인하는데, 이는 폐기해야 될 정점의 답이 여러개인 경우 정점의

번호가 더 작은 것을 먼저 폐기하라고 했기 때문입니다.

K 조건 확인 방법 : node[i] >= k

L 조건 확인 방법 : n - (현재까지 폐기된 정점의수) - node[i] - 1(자기 자신) >= L

이 조건을 만족하지 않는다면 해당 간선을 제거하면 되는데, 마찬가지로 for문을 이용하여 Edge[i][j] 가 존재할 경우

node[j]--; 를 해주면 됩니다. 폐기해야 할 정점이 발견되지 않으면 바이러스 대처가 끝난 상태이므로 현재까지 폐기된 번호를 더한 값을 출력해

주면 됩니다.

4. 어느 마을에서 특정 대피소로 가는 최단거리가 아닌, 어느 마을에서 임의의 대피소 중 가장 가까운 대피소 한 곳을 가면 되기 때문에 각 대피소에서의 최단거리를 모두 찾을 필요가 없습니다. 즉, 가상의 시작점을 잡고, 해당 시작점과 대피소를 모두 가중치가 0인 간선으로 연결을 한 다음, 가상 시작점부터 모든 마을(대피소 포함) 까지의 최단거리를 구하면 다익스트라 1회만으로 모든 최단거리를 구할 수 있습니다. 마을의 범위가 크기 때문에 인접 리스트와 우선순위 큐를 이용한 다익스트라를 구현해야 합니다.

5. 일단 제가 이거로 250점을 받았어야 했는데.. 10회를 초과해서 받지 못했습니다 ㅠㅠ.

신발과 신발을 제작하는 장인, 그리고 특정 신발에 대한 남은 시간을 저장할 수 있는 구조체를 이용하였습니다.

장인들이 일할 수 있는 시간대에 1차원 배열에 값을 1씩 더해줌으로써, 현재 시간대에 몇명의 장인이 일을 할 수 있는지 체크합니다.

그 다음, 남아있는 시간과 신발 인덱스를 포함한 정보를 시간을 저장하는 구조체를 담을 수 있는 우선순위 큐에 넣습니다.

우선순위 큐의 정렬 기준은 시간입니다.

그 다음 해당 시간대에 존재하는 장인의 수요만큼 큐에서 하나씩 꺼내어 일을 처리합니다.

모든 작업을 마치고도 제작이 안된 신발이 있거나, 시간을 체크하는 도중 시간을 초과해버리는 신발이 발견될 경우 0을 출력합니다.

더 좋은 방법 있으신 분은 알려주시면 감사드립니다!