https://www.acmicpc.net/problem/3085
#3085: 사탕 게임
예 3에서는 4행에서 Y와 C를 교체하여 4개의 사탕을 먹을 수 있습니다.
www.acmicpc.net
문제 설명
● 크기가 NXN(N <= 50)인 테이블에 사탕이 있습니다.
● 인접한 사각형 두 개를 선택하고 사탕을 교환합니다.
● 다음은 연속된 가장 긴 동일한 색상의 행 또는 열을 선택하는 문제입니다.
용해 과정
● 인접한 두 사각형을 선택하는 방법의 수를 고려해 봅시다.
우선, NXN 크기 테이블에서 셀을 선택하는 방법의 수는 N^2입니다.
여기서 나머지 이웃 셀을 선택하는 경우의 수는 상, 하, 우, 좌의 모든 경우가 아니다.
오른쪽과 아래만 보세요. 현재 사각형에서 올려다보는 것과 위쪽 사각형에서 내려다보는 것은 같기 때문이다.
현재 셀에서 왼쪽을 보는 것과 왼쪽 셀에서 오른쪽을 보는 것은 같기 때문에 오른쪽과 아래쪽의 경우만 고려한다.
전체 경우의 수를 고려할 수 있습니다. 따라서 (N^2) x 2개의 경우가 가능합니다. –> O(N^2)
● 동일한 색상의 가장 긴 연속 행 또는 열 선택은
어느 부분이 가장 긴 행 또는 열인지 모르기 때문에 전체 부분을 확인해야 합니다. –> O(N^2)
● 따라서 전체 시간 복잡도는 O(N^4)가 됩니다.
그러나 문제에서 N의 범위는 50보다 작거나 같기 때문에,
50^4 = 최대 6250000개의 경우를 계산할 수 있으므로 무차별 대입 문제로 해결할 수 있습니다.
암호
