BOJ 14500 : 테트로미노 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/14500

 

 

블럭은 5종류지만, 회전이나 대칭을 시켜도 되므로 총 19종류가 된다.

 

 

이 블럭을 실제로 4x4 배열로 만들면 아래의 모양이 된다.

/* 19개 블럭을 4x4 배열로 선언 */
int BLOCK[19][4][4] =
{
	{ 
		{ 1, 1, 1, 1 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 0, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 1, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 0, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 1, 0 },
		{ 1, 0, 0, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 0, 0 },
		{ 0, 1, 0, 0 },
		{ 0, 1, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 0, 0, 1, 0 },
		{ 1, 1, 1, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{
		{ 0, 1, 0, 0 },
		{ 0, 1, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 0, 0, 0, 0 }
	},
	{ 
		{ 1, 0, 0, 0 },
		{ 1, 1, 1, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 1, 0 },
		{ 0, 0, 1, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{
		{ 1, 0, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 0, 1, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{
		{ 0, 1, 1, 0 },
		{ 1, 1, 0, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 0, 1, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 0, 0 },
		{ 0, 1, 1, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 1, 0 },
		{ 0, 1, 0, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 0, 1, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 0, 1, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 0, 1, 0, 0 },
		{ 1, 1, 1, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 0, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
};

 

먼저 첫번째 예제 입력에 대한 출력 19가 어떻게 나왔는지 보자.

5 x 5 map에서 아래의 테트로미노를 통해 답이 19(6 + 5 + 4 + 4)가 최대임을 알 수 있다.

 

그러나 실제로 만든 BLOCK으로 scan하면 5 x 5를 초과하기 때문에, MAP을 넉넉하게 잡고 주변을 0으로 만들어 둔다.

 

그러면 MAP의 r, c를 기준으로 4 x 4 만큼 Block의 각 (r, c)와 MAP의 (r, c)의 값을 곱해서 더하면,

최종 합을 구할 수 있고, 매번 최종 합 중 가장 큰 값을 갱신하면 된다.

int scan(int b, int r, int c) /* MAP의 좌표 r, c */
{
	int sum = 0;

	/* MAP에서 4 x 4 의 Block에 해당하는 값을 계산 */
	for (int dr = 0; dr < 4; dr++)
		for (int dc = 0; dc < 4; dc++)
			sum += MAP[r + dr][c + dc] * BLOCK[b][dr][dc];

	return sum;
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (500+50)

int N, M;
int MAP[MAX][MAX];

int BLOCK[19][4][4] =
{
	{ 
		{ 1, 1, 1, 1 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 0, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 1, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 0, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 1, 0 },
		{ 1, 0, 0, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 0, 0 },
		{ 0, 1, 0, 0 },
		{ 0, 1, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 0, 0, 1, 0 },
		{ 1, 1, 1, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{
		{ 0, 1, 0, 0 },
		{ 0, 1, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 0, 0, 0, 0 }
	},
	{ 
		{ 1, 0, 0, 0 },
		{ 1, 1, 1, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 1, 0 },
		{ 0, 0, 1, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{
		{ 1, 0, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 0, 1, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{
		{ 0, 1, 1, 0 },
		{ 1, 1, 0, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 0, 1, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 0, 0 },
		{ 0, 1, 1, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 1, 1, 0 },
		{ 0, 1, 0, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 0, 1, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 0, 1, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 0, 1, 0, 0 },
		{ 1, 1, 1, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
	{ 
		{ 1, 0, 0, 0 },
		{ 1, 1, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 0, 0, 0, 0 } 
	},
};


void input()
{
	scanf("%d %d", &N, &M);

	for (int r = 0; r < N; r++)
		for (int c = 0; c < M; c++)
			scanf("%d", &MAP[r][c]);
}

void output()
{
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < M; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

int scan(int b, int r, int c)
{
	int sum = 0;

	for (int dr = 0; dr < 4; dr++)
		for (int dc = 0; dc < 4; dc++)
			sum += MAP[r + dr][c + dc] * BLOCK[b][dr][dc];

	return sum;
}

int main(void)
{
	int max, tmp;

	input();

	tmp = max = 0;
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < M; c++)
		{
			for (int k = 0; k < 19; k++)
			{
				tmp = scan(k, r, c);
				if (max < tmp) max = tmp;
			}
		}
	}

	printf("%d\n", max);

	return 0;
}

 

마지막으로, tc가 여러 개이므로 실제 시험에서는 tc 버전으로 바꾸자.

int main(void)
{

	int T;
	scanf("%d", &T);
    
    for (int tc = 1; tc <= T; tc++)
    {
        int max, tmp;
    	
        input();
    	
        ...
        
        printf("#%d %d\n", tc, max);
    }
   
	return 0;
}