[백준 14500번 C/C++] 테트로미노
[백준 14500번 C/C++] 테트로미노

https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
해결방안
Brute Force (브루트 포스)
구현
코드
#include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; int n, m; vector<vector<int>> v; int sum1, sum2, sum3, sum4, sum5, sum6, sum7, sum8, sum9, sum10; int maxValue1, maxValue2, maxValue3, maxValue4, maxValue5, maxValue6, maxValue7, maxValue8, maxValue9, maxValue10, maxValue; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; v.resize(n+4, vector<int>(m+4)); for (int y = 0; y < n; y++) { for (int x = 0; x < m; x++) { cin >> v[y][x]; } } //주황색 int dirY[6] = { 0, 0, 1, 1, 2, 2 }; int dirX[6] = { -1, 1, -1, 1, -1, 1 }; int dirYY[6] = { -1, 1, -1, 1, -1, 1 }; int dirXX[6] = { 0, 0, 1, 1, 2, 2}; //보라색 int dirYYY[2] = { -1, 1 }; int dirXXX[2] = { -1, 1 }; for (int y = 0; y < n; y++) { for (int x = 0; x < m; x++) { //하늘색 sum1 = v[y][x] + v[y + 1][x] + v[y + 2][x] + v[y + 3][x]; sum2 = v[y][x] + v[y][x + 1] + v[y][x + 2] + v[y][x + 3]; if (maxValue1 < sum1) maxValue1 = sum1; if (maxValue2 < sum2) maxValue2 = sum2; //노란색 sum3 = v[y][x] + v[y][x + 1] + v[y + 1][x] + v[y + 1][x + 1]; if (maxValue3 < sum3) maxValue3 = sum3; //주황색, 보라색 for (int i = 0; i < 6; i++) { if (x < 1) { if (i == 0 || i == 2 || i == 4) continue; else sum4 = v[y][x] + v[y + 1][x] + v[y + 2][x] + v[y + dirY[i]][x + dirX[i]]; } else { sum4 = v[y][x] + v[y + 1][x] + v[y + 2][x] + v[y + dirY[i]][x + dirX[i]]; } if (maxValue4 < sum4) maxValue4 = sum4; } for (int i = 0; i < 6; i++) { if (y < 1) { if (i == 0 || i == 2 || i == 4) continue; else sum5 = v[y][x] + v[y][x + 1] + v[y][x + 2] + v[y + dirYY[i]][x + dirXX[i]]; } else { sum5 = v[y][x] + v[y][x + 1] + v[y][x + 2] + v[y + dirYY[i]][x + dirXX[i]]; } if (maxValue5 < sum5) maxValue5 = sum5; } //초록색 sum6 = v[y + 1][x] + v[y + 1][x + 1] + v[y][x + 1] + v[y][x + 2]; sum7 = v[y][x] + v[y][x + 1] + v[y + 1][x + 1] + v[y + 1][x + 2]; sum8 = v[y][x] + v[y+1][x] + v[y+1][x+1] + v[y+2][x+1]; sum9 = v[y][x + 1] + v[y + 1][x] + v[y + 1][x + 1] + v[y + 2][x]; if (maxValue6 < sum6) maxValue6 = sum6; if (maxValue7 < sum7) maxValue7 = sum7; if (maxValue8 < sum8) maxValue8 = sum8; if (maxValue9 < sum9) maxValue9 = sum9; } maxValue = max(maxValue9, max(maxValue8, max(maxValue7, max(maxValue6, max(maxValue5, max(maxValue4, max(maxValue3, max(maxValue1, maxValue2)))))))); } cout << maxValue; return 0; }
더 나은 풀이
#include <iostream> #include <cmath> using namespace std; int n, m, A[502][502]; int dy[] = { -1, 0, 0, 1 }, dx[] = { 0, -1, 1, 0 }; int DFS(int y, int x, int d) { if (d == 4) return 0; int ret = 0, a = A[y][x], ny, nx; A[y][x] = 0; for (int i = 0; i < 4; i++) if (A[ny = y + dy[i]][nx = x + dx[i]]) ret = max(ret, DFS(ny, nx, d + 1)); return (A[y][x] = a) + ret; } int Tetro(int y, int x) { int sum = A[y][x], ret = 0; for(int i=0; i<4; i++) sum += A[y + dy[i]][x + dx[i]]; for (int i = 0; i < 4; i++) ret = max(ret, sum - A[y + dy[i]][x + dx[i]]); return ret; } int main() { int ans = 0, y, x; cin >> n >> m; for (y = 1; y <= n; y++) for (x = 1; x <= m; x++) cin >> A[y][x]; for (y = 1; y <= n; y++) for (x = 1; x <= m; x++) ans = max(max(ans, DFS(y, x, 0)), Tetro(y, x)); cout << ans; }
DFS를 활용하여 푼 더 나은 풀이다. 실행속도는 더 느리지만 풀이가 더 정형화되어 좋다.
'⭐ 코딩테스트 > 백준' 카테고리의 다른 글
[백준 2110번 C/C++] 공유기 설치 (0) | 2023.07.12 |
---|---|
[백준 1927번 C/C++] 최소 힙 (0) | 2023.07.11 |
[백준 20920번 C/C++] 영단어 암기는 괴로워 (0) | 2023.07.09 |
[백준 2108번 C/C++] 통계학 (0) | 2023.07.08 |
[백준 1916번 C/C++] 최소비용 구하기 (0) | 2023.07.07 |
댓글
이 글 공유하기
다른 글
-
[백준 2110번 C/C++] 공유기 설치
[백준 2110번 C/C++] 공유기 설치
2023.07.12 -
[백준 1927번 C/C++] 최소 힙
[백준 1927번 C/C++] 최소 힙
2023.07.11 -
[백준 20920번 C/C++] 영단어 암기는 괴로워
[백준 20920번 C/C++] 영단어 암기는 괴로워
2023.07.09 -
[백준 2108번 C/C++] 통계학
[백준 2108번 C/C++] 통계학
2023.07.08
댓글을 사용할 수 없습니다.