SWEA 2112 - [모의 SW 역량테스트] 보호 필름

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

예전 기억으로는, 삼성 SW 역량 테스트 준비용 샘플 문제가 하나밖에 없었는데 뭔가 많이 추가된 모양이다.

이번 문제는 그 중 하나이다.

삼성 SW 역량 테스트에는 이런 백트래킹류의 탐색 문제가 자주 나오는 것 같다.

문제

문제를 요약하자면, 세로 길이가 D이고 가로 길이가 W인 2차원 평면에서, 특정 조건에 맞추기 위해 어떤 행을 모두 A(0) 또는 B(1)로 바꾸는 횟수를 최소로 하고 싶다는 것이다.

여기서 조건은, 모든 세로줄에서 같은 종류끼리 K개 이상 연속으로 붙어 있으면 되게 만드는 것이다.

어떤 행을 선택하는 조합이 여러개이므로 조합 문제일거라 생각했고, 역시나 행이 13개 밖에 없으니 \(n^{13}\) 이면 충분하겠더니 생각했다.

"어떤 행을 고른다/고르지 않는다" 라면 \(2^{13}\) 으로 끝나겠지만, 선택지는 총 3개이다.

1. 어떤 행을 고르지 않는다.
2. 어떤 행을 모두 A로 바꾼다.
3. 어떤 행을 모두 B로 바꾼다.

그럼 \(3^{13}\) 개의 가짓수가 나오는데, \(2^{13}\)에 비하면 200배는 많다. 조건 만족을 확인하느라 가로*세로(W*D) 만큼 확인한다고 치면, \(O(3^{13}WD)\)는 얼추 4억에 가깝다. 테스트케이스가 50개인것까지 고려하면.... 흠....

문제를 자세히 살피면, 사실 어떤 행을 K개보다 많이 고를 필요가 없다는 점이 보인다.

위에서부터 K개의 줄을 전부 같은 종류로 바꿔버리면 그만이기 때문이다. 이러면 \(O(3^kWD)\) 로 바뀌기는 하지만, 문제 조건이 \(1 \le k \le D \le 13\) 이라서 사실 다르지는 않다. 확률상 줄었을 뿐이다.

재귀 함수를 가지치기해서 탐색 횟수를 줄일 수도 있을 것 같다.

고르는 행의 개수를 1개, 2개, ..., k개씩 늘려가며 각 조합(permutation)들을 하나씩 해보는것도 좋은 방법이지만, 정답을 받았으니 우선 미루어본다.

코드