예제. 문제 : BOARDCOVER
https://algospot.com/judge/problem/read/BOARDCOVER
1) 문제를 읽고 이해하기
- 시간제한 2ms / 메모리제한 2^16kb
- 1 <= h, w <= 20 / 흰칸의 수 <= 50
2) 문제 재정의
- 게임판의 흰칸( . )을 'ㄱ' 모양을 회전시킨 모양으로 전부 덮을 수 있는 경우의 수
3) 계획 세우기
- 경우의 수 문제이기에 일단 다해보는 '브루트 포스'
: 블럭을 채워야 할 칸을 선택 후 적절한 블럭을 채움
: 아직 채우지 않은 칸을 대상으로 위 과정을 반복함
=> '한 블럭'과 '나머지 칸'으로 문제를 분할 => 재귀
- 한 지점에서 시작하여 채우는 모양의 경우의 수가 16개
최대 칸의 개수가 400개 이므로 중복되는 경우를 줄일 필요가 있음
- 재귀 호출 시 마다 젤 왼쪽 윗칸을 채우도록 순서를 강제함
그럼 어떤 칸을 채우려고 할 때, 그 칸보다 왼쪽 윗칸은 다 차있다고 가정할 수 있음
<fig 1> <fig 2> <fig 3> <fig 4>
- 위 그림처럼 현재칸( * )을 채우는 경우의 수는 4가지
4) 계획 검증하기
- 시간복잡도 : 한 칸에서 선택할 수 있는 블럭 모양이 4가지 이므로
4 ^ 16(흰칸의 개수가 최대 50개라고 했으니 3개짜리 블럭은 최대 16개를 넣을 수 있음)
≒ 4000 억
하지만, 재귀가 4000억을 다 돌지 않음. 그 이유는 한개의 블럭이 결정 되면 다음에 결정될 블럭의 경우의 수는 줄어듬
ex) 2*3 모두 하얀칸인 경우
<fig 1>을 선택하면 재귀 1 --- 경우의 수 0
<fig 2>를 선택하면 재귀 2 --- 경우의 수 1
<fig 3>을 선택하면 재귀 2 --- 경우의 수 1
<fig 4>를 선택하면 재귀 0 --- 경우의 수 0
즉, 실제로 재귀 5번 --- 모든 칸을 채울수 있는 경우의 수는 2
2개의 블럭을 놓는 이론적인 경우의 수는 4^2 = 16가지
2개의 블럭을 놓는 경우의 수에서 재귀가 도는 횟수가 많이 줄어듬
※ 실제로는 12칸일 경우 재귀는 23번
48칸일 경우 재귀는 68655번
※ 줄어드는건 알 수 있지만 그래도 어떻게 저 경우의 수가 시간 내에 들어오리라는 확신을 할 수가 있을까?
확신을 해야만 브루트 포스로 풀텐데
- 공간복잡도 : global variable : int * 2 + int * 12 * 2 = 104byte
local variable : int * 400 = 1600byte(int나, bool 변수들은 무시)
즉, 1804byte < 2^16kb
5, 6) 계획 수행하기 및 회고하기
- 솔직히 아직도 재귀가 시간내에 들어오리란 확신을 가지지 못하겠음...
- 4가지 경우의 수를 줄일 때 처음에 '중심'을 가지고 줄였음
하지만, 다음 중심을 찾기가 너무 어렵고, 중심이 들어가지 않는 경우가 발생한다면 그 부분에서 계속 무한루프를 돌게됨
알고스팟 예제에서 첫 번째 흰칸을 중심이 들어갈 경우로 판단한다면 아무것도 넣을 수가 없음. 만약 건너뛰게 한다 하더라도
다음번 시작점을 찾을 때도 (0, 0) 에서 시작하기에 저 부분을 계속 거치게 됨
그래서 왼쪽 위를 무조건 채운다는 강제를 부여하게 되면 위 그림과 같은 4가지 경우가 생김
소스코드
- 알고리즘 문제 해결전략 1편 중 -
- 저작권 문제시 삭제하겠습니다 -
'먹고살려면 > Algorithm' 카테고리의 다른 글
| 4편 그래프 : dfs 1 (0) | 2017.12.29 |
|---|---|
| 3-3편 무식하게 풀기 3 (0) | 2017.12.20 |
| 번외편 c/c++ 입력속도 (0) | 2017.12.12 |
| 3-1편 무식하게 풀기 1 (0) | 2017.12.11 |
| 2편 알고리즘 시간 복잡도 분석 (0) | 2017.12.07 |