Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변�
www.acmicpc.net
풀이
테트로미노는 문제에서 나오는 5가지의 모형을 대칭, 회전시키면 총 19개의 고정 형태의 테트로미노가 나온다.
종이의 크기는 500이하로, 19가지의 모형을 모두 대입해서 모든 경우의 수를 구하는 게 충분히 가능하다.
이를 구현하기 위해서 (0,0)인 현재 위치로 부터 상대적인 위치를 저장한 int tetrominoModel[19][3][2] 가 필요한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
int tetrominoModel[19][3][2]={
{{0,1},{0,2},{0,3}},
{{1,0},{2,0},{3,0}},
{{0,1},{1,0},{1,1}},
{{0,1},{0,2},{1,0}},
{{0,1 },{0,2 },{1,2 }},
{{0,1 },{1,1 },{2,1 }},
{{0,1 },{ -1,1},{-2,1 }},
{{ 0,1},{0,2 },{-1,2 }},
{{ 1,0},{1,1 },{1,2 }},
{{ 1,0},{2,0 },{2,1 }},
{{0,1 },{1,0 },{2,0 }},
{{1,0 },{ 1,1},{2,1 }},
{{-1,1 },{0,1 },{1,0 }},
{{ -1,1},{-1,2 },{0,1 }},
{{ 0,1},{1,1 },{1,2 }},
{{ -1,1},{0,1 },{0,2 }},
{{ 1,0},{1,1 },{2,0 }},
{{ 0,1},{ 0,2},{1,1 }},
{{-1,1},{0,1 },{1,1 }}
};
|
cs |
기준 위치가 되는 (0,0)은 테트로미노의 모형의 가장 왼쪽 중에 가장 위를 기준으로 한다.
이제 위의 모형의 번호를 매개변수로 받아 종이판에 모두 대입해 보는 void FindMaxTetromino(int modelIdx)를 구현한다.
line 43~48을 보면 아래와 같은 코드가 등장하는데
|
1
2
3
4
5
6
|
if( rNow - 2<0 || row <= rNow +3 || column <= cNow+3 )
for(int i=0; i<3 ; ++i)
if( !(0<=rNow+ret[i][0] && rNow+ret[i][0] <row && cNow+ret[i][1] < column)){
isPosTet = false;
break;
}
|
cs |
우리가 작성한 모형의 기준점은 가장 왼쪽이므로 column은 기준점에서 0~3을 더해준다. 따라서 종이를 벗어나는지 판단하는 코드는 column <= cNow+3 인 경우에만 해주어도 된다. 동일한 이유로 row는 기준점에서 -2~ +3을 해주기 때문에 rNow - 2<0 || row <= rNow +3 를 확인한다.
이러한 경우에만 범위를 확인한다면, 항상 범위를 확인하는 것보다 효율적이다.
코드
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No.17135 - 캐슬 디펜스 (C++) (0) | 2020.10.25 |
|---|---|
| [백준] No. 1038 - 감소하는 수 (C++) (0) | 2020.10.24 |
| [백준] NO.12100 - 2048 (Easy)(C++) (0) | 2020.10.19 |
| [백준]No.2580 - 스도쿠 (C++) (0) | 2020.08.29 |
| [백준] No.9663 - N-Queen (C++) (0) | 2020.08.18 |