삼성 sw 역량 테스트 - 테트로미노(14500번)

1. 개요

 삼성 sw 역량 테스트 기출 문제인 테트로미노를 풀어보겠습니다. 이번문제는 DFS가 필요없는 단순 문제이기 때문에 아래와 같은 구조를 사용하지 않습니다.

2. 문제 분석

 백준 홈페이지의 문제에서 명시된 조건들은 다음과 같습니다.

    ① 가로, 세로 크기는 4<N, M<500 입니다.

    ② 주어진 모양 5가지는 회전, 대칭이 가능합니다.

    ③ 입력으로 주어지는 수는 1000을 넘지 않습니다.

    ④ 주어진 2차원 배열에서 테트로미노가 놓인 칸에 쓴인 수의 합의 최대값을 찾는다.

    

3. 소스코드

 이번 문제는 상하좌우 문제이기 때문에 기준으로부터 상하좌우에 대해 확인을 해야합니다. 또한, 상하좌우 중 하나만 함수를 완벽하게 완성시키면 복붙과 간단한 수정으로 문제를 해결할 수 있습니다.  저는 주어진 배열이 10x10이라면 각 100개의 요소가 기준이 되어 총 100번의 비교를 하였습니다.

 우선 기준에서 아래로 테트로미노가 놓인가 가정하고 값을 확인하는 함수를 보겠습니다.

 코드를 보시면서 "어 왜 보라색 테트로미노는 대칭이 없지?"라는 의문이 드실수 있습니다. 그 이유는 기준에서 위로 테트로미노를 놓으면 대칭과 같은 모양이 되기 때문입니다. 실질적으로 모든 경우의 수를 가정해보면 일자 모양과 정사각형 모양도 중복이 발생합니다.  네 그렇다구요. 

전체 코드입니다.

#include<iostream> #define MAX(X,Y) ((X)>(Y)?(X):(Y)) using namespace std; int arr[501][501]; int N_raw, M_col; int result=0; void check_Down(int raw, int col) { int sub_result = 0; int temp; if (raw + 3 < N_raw) { temp = 0; for (int i = 0; i < 4; i++) { temp += arr[raw + i][col]; } sub_result = MAX(sub_result, temp); } if (raw + 2 < N_raw ) { int twoBlock = arr[raw][col] + arr[raw + 1][col]; int threeBlock = twoBlock + arr[raw + 2][col]; if (col + 1 < M_col) { temp = twoBlock + arr[raw][col + 1] + arr[raw + 1][col + 1]; sub_result = MAX(sub_result, temp); temp = twoBlock + arr[raw + 2][col + 1] + arr[raw + 1][col + 1]; sub_result = MAX(sub_result, temp); temp = threeBlock + arr[raw + 1][col + 1]; sub_result = MAX(sub_result, temp); temp = threeBlock + arr[raw + 2][col + 1]; sub_result = MAX(sub_result, temp); } if (col - 1 > -1) { temp = twoBlock + arr[raw + 2][col - 1] + arr[raw + 1][col - 1]; sub_result = MAX(sub_result, temp); temp = threeBlock + arr[raw + 2][col - 1]; sub_result = MAX(sub_result, temp); } } result = MAX(sub_result, result); } void check_Right(int raw, int col) { int sub_result = 0; int temp; if (col + 3 < M_col) { temp = 0; for (int i = 0; i < 4; i++) { temp += arr[raw][col + i]; } sub_result = MAX(sub_result, temp); } if (col + 2 < M_col){ int twoBlock = arr[raw][col] + arr[raw][col + 1]; int threeBlock = twoBlock + arr[raw][col + 2]; if (raw - 1 > -1) { temp = twoBlock + arr[raw - 1][col] + arr[raw - 1][col + 1]; sub_result = MAX(sub_result, temp); temp = twoBlock + arr[raw - 1][col + 2] + arr[raw - 1][col + 1]; sub_result = MAX(sub_result, temp); temp = threeBlock + arr[raw - 1][col + 1]; sub_result = MAX(sub_result, temp); temp = threeBlock + arr[raw - 1][col + 2]; sub_result = MAX(sub_result, temp); } if (raw + 1< N_raw) { temp = twoBlock + arr[raw + 1][col + 2] + arr[raw + 1][col + 1]; sub_result = MAX(sub_result, temp); temp = threeBlock + arr[raw + 1][col + 2]; sub_result = MAX(sub_result, temp); } } result = MAX(sub_result, result); } void check_Up(int raw, int col) { int sub_result = 0; int temp; if (raw - 3 > -1) { temp = 0; for (int i = 0; i < 4; i++) { temp += arr[raw - i][col]; } sub_result = MAX(sub_result, temp); } if (raw - 2 > -1) { int twoBlock = arr[raw][col] + arr[raw - 1][col]; int threeBlock = twoBlock + arr[raw - 2][col]; if (col - 1 > -1) { temp = twoBlock + arr[raw][col - 1] + arr[raw - 1][col - 1]; sub_result = MAX(sub_result, temp); temp = twoBlock + arr[raw - 2][col - 1] + arr[raw - 1][col - 1]; sub_result = MAX(sub_result, temp); temp = threeBlock + arr[raw - 1][col - 1]; sub_result = MAX(sub_result, temp); temp = threeBlock + arr[raw - 2][col - 1]; sub_result = MAX(sub_result, temp); } if (col + 1 < M_col) { temp = twoBlock + arr[raw - 2][col + 1] + arr[raw - 1][col + 1]; sub_result = MAX(sub_result, temp); temp = threeBlock + arr[raw - 2][col + 1]; sub_result = MAX(sub_result, temp); } } result = MAX(sub_result, result); } void check_Left(int raw, int col) { int sub_result = 0; int temp; if (col - 3 > -1) { temp = 0; for (int i = 0; i < 4; i++) { temp += arr[raw][col - i]; } sub_result = MAX(sub_result, temp); } if (col - 2 > -1) { int twoBlock = arr[raw][col] + arr[raw][col - 1]; int threeBlock = twoBlock + arr[raw][col - 2]; if (raw + 1 < N_raw) { temp = twoBlock + arr[raw + 1][col] + arr[raw + 1][col - 1]; sub_result = MAX(sub_result, temp); temp = twoBlock + arr[raw + 1][col - 2] + arr[raw + 1][col - 1]; sub_result = MAX(sub_result, temp); temp = threeBlock + arr[raw + 1][col - 1]; sub_result = MAX(sub_result, temp); temp = threeBlock + arr[raw + 1][col - 2]; sub_result = MAX(sub_result, temp); } if (raw - 1 > -1) { temp = twoBlock + arr[raw - 1][col - 2] + arr[raw - 1][col - 1]; sub_result = MAX(sub_result, temp); temp = threeBlock + arr[raw - 1][col - 2]; sub_result = MAX(sub_result, temp); } } result = MAX(sub_result, result); } int main() { cin >> N_raw >> M_col; for (int i = 0; i < N_raw; i++) { for (int j = 0; j < M_col; j++) { cin >> arr[i][j]; } } for (int i = 0; i < N_raw; i++) { for (int j = 0; j < M_col; j++) { check_Down(i, j); check_Up(i, j); check_Left(i, j); check_Right(i, j); } } cout << result; }