14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
먼저 노트와 펜을 준비한다.
블록의 한 칸을 (y,x)로 잡은다음 나머지 3칸을 기준점과 비교해 y,x 좌표를 적어보자.
그리고 5가지 블록의 회전 모양과 그것을 대칭했을 때 모양에 대한 y,x좌표를 전부 적는다.
적은 내용을 바탕으로 나올 수 있는 블록 모양을 배열에 담고 보드 (0,0) 좌표에서부터 (N-1,N-1) 까지 모든 칸에 블록을 대보고 그 중에서 최대 점수를 maxScore변수에 저장하고 출력하면 원하는 결과를 얻을 수 있다.
|
#include <iostream>
#include <vector>
using namespace std;
const int dy[19][4] = {
{0,0,0,0}, {0,1,2,3}, // ㅡ
{0,0,1,1}, // ㅁ
{0,1,2,2}, {0,0,0,1}, {0,0,1,2}, {0,0,0,-1}, {0,1,2,2}, {0,0,0,1}, {0,0,1,2}, {0,1,1,1}, // ㄴ
{0,1,1,2}, {0,0,-1,-1}, {0,1,0,-1}, {0,0,1,1}, // ㄱㄴ
{0,0,0,1}, {0,1,2,1}, {0,1,1,1}, {0,1,1,2} // ㅜ
};
const int dx[19][4] = {
{0,1,2,3}, {0,0,0,0}, // ㅡ
{0,1,0,1}, // ㅁ
{0,0,0,1}, {0,1,2,0}, {0,1,1,1}, {0,1,2,2}, {0,0,0,-1}, {0,1,2,2}, {0,1,0,0}, {0,0,1,2}, // ㄴ
{0,0,1,1}, {0,1,1,2}, {0,0,1,1}, {0,1,1,2}, // ㄱㄴ
{0,1,2,1}, {0,0,0,-1}, {0,-1,0,1}, {0,0,1,0} // ㅜ
};
int board[501][501];
int maxCol, maxRow;
int maxScore = -987654321;
int max(int a, int b) { return a > b ? a : b; }
void SetBlock(int startY, int startX)
{
int sum;
for (int i = 0; i < 19; i++)
{
sum = 0;
for (int j = 0; j < 4; j++)
{
if (startY + dy[i][j] < 0 || startY + dy[i][j] >= maxCol ||
startX + dx[i][j] < 0 || startX + dx[i][j] >= maxRow)
continue;
sum += board[startY + dy[i][j]][startX + dx[i][j]];
}
maxScore = max(maxScore, sum);
}
}
void Solution()
{
for (int i = 0; i < maxCol; i++)
for (int j = 0; j < maxRow; j++)
SetBlock(i, j);
}
int main(void)
{
cin >> maxCol >> maxRow;
for(int i=0; i<maxCol; i++)
for (int j = 0; j < maxRow; j++)
{
cin >> board[i][j];
}
Solution();
cout << maxScore << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 10day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 1065번: 한수 (0) | 2020.04.17 |
|---|---|
| 백준 15686번: 치킨 배달 (C++) (0) | 2020.04.15 |
| 백준 14889번: 스타트와 링크 (0) | 2020.04.14 |
| 백준 1018번: 체스판 다시 칠하기 (0) | 2020.04.13 |
| 백준 1182번: 부분수열의 합 (0) | 2020.04.13 |