1. 지뢰찾기디스크립션에 매우 중요한 내용이 누락되어 있는데, 외곽선만 숫자가 공개되어 있으며 외곽선이 아닌 부분은 숫자가 전혀 써져있지 않다. 고로 외곽선과 붙어있는 영역에만 지뢰가 있을 수도 없을 수도 있는 것이고, 그렇지 않은 n-4 * n-4 영역에는 지뢰가 무조건 있다고 가정해도 된다. 최대화가 목표이기 때문이다. 외곽선과 붙어있는 영역의 지뢰를 최대화하라고 하지만, 사실 지뢰의 개수를 유일하게 결정할 수 있다. 모서리에 있는 지뢰를 제외한 모든 지뢰는 주위 3개의 셀에게 노출된다. 즉 모서리 지뢰를 제거하면 나머지 지뢰의 수는 적혀있는 숫자의 합 / 3 이라는 것이다. 모서리에 있는 지뢰는 모서리에 있는 숫자로 존재 여부를 결정할 수 있으니, 이를 결정하고 나머지 숫자의 합을 세주면 된다. n
1. Arrays 두 행과 열을 바꾼다는 것이 무슨 뜻인지 먼저 생각해 보자. 각각의 행과 열에 대해서 순열 P[i]와 Q[i]를 정의하자. P[i] = (현재 i번 행의 원래 위치), Q[i] = (현재 i번 열의 원래 위치) 라고 하면, 두 행을 바꾸는 것은 단순히 P[i]와 P[j]를 바꾸고, 열을 바꾸는 것은 단순히 Q[i]와 Q[j]를 바꾸는 것이다. 고로 우리가 주어진 연산으로 할 수 있는 것은 P와 Q를 임의의 순열로 섞는 것이니, A와 B가 닮았다 (alike) 는 것은 A[P[i]][Q[j]] = B[i][j] 를 만족하는 순열 P, Q가 존재한다는 것과 동치이다. 모든 수가 다르니, 각 수가 A에서 어떤 위치, B에서 어떤 위치에 있는지를 유일하게 결정할 수 있다. 즉 P[i] = j,..
1. 전구편의상 왼쪽 스위치와 오른쪽 전구의 번호가 1 2 3 4.. 처럼 순서대로 되어 있다고 하자. p[i] = (왼쪽 i번 스위치를 눌렀을 때 켜진 오른쪽 전구의 번호) 라 하자. 전선이 교차하지 않게 왼쪽에서 {i1, i2, i3, ... ik} 스위치를 켰다는 것은, p[i1] < p[i2] < p[i3] < ... < p[ik] 라는 것과 동치이다. 이렇게 최대 개수의 스위치를 켜는 것은, 최장 증가 부분 수열 (LIS) 문제와 동일하다. 이는 동적 계획법으로 O(N^2)에 찾고 역추적도 할 수 있다. (만약 방법을 모른다면, dp[i] = i번 수에서 끝나는 최대 길이의 LIS라 정의하고 생각해 보자.)왼쪽 스위치와 오른쪽 전구의 번호가 실제로 1 2 3 4가 아니라는 것이 문제인데, 그냥 ..
- Total
- Today
- Yesterday