다이아몬드 광산, 미네랄 2

다이아몬드 광산 (P5)

• https://www.acmicpc.net/problem/1028

풀이

• R과 C제한이 750이고, 다이아몬드 광산의 최대 크기는 375이다.

• 현재 위치(x, y)에서 왼쪽 위로 갈 수 있는 최대 길이와 오른쪽 위로 갈 수 있는 최대 길이를 구한다.

• d[x][y][0] : 왼쪽 위로 갈 수 있는 최대 길이

• d[x][y][1] : 오른쪽 위로 갈 수 있는 최대 길이

• (1, 1) ~ (R, C) 까지 탐색하면서 해당 꼭짓점을 가장 아래에 위치하는 꼭짓점이라고 가정했을 경우, 만들 수 있는 최대길이값들 중에서 가장 큰 값이 정답이 된다.

• (x, y)를 기준으로 왼쪽위로 k만큼, 오른쪽위로 k만큼 갈 수 있고, 왼쪽 위의 꼭짓점 (x - k, y - k)에서 오른쪽 위로 k만큼 갈 수 있고, 오른쪽 위의 꼭짓점 (x - k, y + k)에서 왼쪽 위로 k만큼 갈 수 있으면 다이아몬드가 완성된다.
  

• 시간복잡도 : O(RC log max(R,C))

• 분류

  • 전처리
  • 완전 탐색

미네랄 2

• https://www.acmicpc.net/problem/18500

풀이

• '공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다.' 라는 조건때문에 미네랄을 먼저 파괴하고 난 뒤 땅에서부터 연결된 미네랄들을 체크를 하면 체크되지 않은 미네랄들은 공중에 뜬 미네랄들이 된다.

• 체크되지 않은 미네랄들을 탐색하면서 최소로 내려가야할 거리를 구한 다음, 해당 거리만큼 내려주면 된다.

• 주의할 점은 최소로 내려가야할 거리를 구할 때 모든 미네랄들을 탐색해줘야한다는 점! 나는 땅에서 가장 가까운 미네랄들만 탐색하면 되는 줄 알았는데 반례가 존재하였다. 그 반례를 해결했더니 정답!