티스토리 뷰
문제 링크입니다.
https://www.acmicpc.net/problem/14500
풀이 방법
브루트포스 알고리즘을 사용합니다.
테트로미노는 5개의 모양를 가지지만 상하좌우 방향을 달리함에 따라 19개의 모양을 가집니다.
이러한 19개의 모양을 shape 배열에 저장해놓고,
모든 칸을 순회하며 각 칸에 19개의 모양을 대입합니다.
순회를 진행하면서 각 모양마다 속한 칸의 숫자들을 더하고 비교 연산을 통해 최댓값을 구합니다.
풀이
//
// main.cpp
// 14500
//
// Created by Jihye on 2020/04/26.
// Copyright © 2020 Jihye Han. All rights reserved.
//
#include <iostream>
using namespace std;
int n, m; // 행, 열의 크기
int board[500][500]; // 종이
int ans = 0; // 최대합
const int shape[19][4][2] = {
{ {0,0}, {0,1}, {1,0}, {1,1} },
{ {0,0}, {0,1}, {0,2}, {0,3} },
{ {0,0}, {1,0}, {2,0}, {3,0} },
{ {0,0}, {0,1}, {0,2}, {1,0} },
{ {0,2}, {1,0}, {1,1}, {1,2} },
{ {0,0}, {1,0}, {1,1}, {1,2} },
{ {0,0}, {0,1}, {0,2}, {1,2} },
{ {0,0}, {1,0}, {2,0}, {2,1} },
{ {0,0}, {0,1}, {1,1}, {2,1} },
{ {0,0}, {0,1}, {1,0}, {2,0} },
{ {0,1}, {1,1}, {2,0}, {2,1} },
{ {0,0}, {1,0}, {1,1}, {2,1} },
{ {0,1}, {1,0}, {1,1}, {2,0} },
{ {0,1}, {0,2}, {1,0}, {1,1} },
{ {0,0}, {0,1}, {1,1}, {1,2} },
{ {0,0}, {0,1}, {0,2}, {1,1} },
{ {0,1}, {1,0}, {1,1}, {1,2} },
{ {0,1}, {1,0}, {1,1}, {2,1} },
{ {0,0}, {1,0}, {1,1}, {2,0} }
};
void tetromino(int x, int y) {
// 19개의 테트로미노 모양 대입하기
for (int i = 0; i < 19; i++) {
int temp = 0;
for (int j = 0; j < 4; j++) {
int tx = x + shape[i][j][0];
int ty = y + shape[i][j][1];
if (tx >= 0 && tx < n && ty >= 0 && ty < m) {
temp += board[tx][ty];
}
}
if (ans < temp) ans = temp;
}
}
void solve() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
tetromino(i, j);
}
}
printf("%d\n", ans);
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &board[i][j]);
}
}
solve();
return 0;
}
'Dev.CodingTest > BACKJOON' 카테고리의 다른 글
[백준 c++] 14502번 : 연구소 (0) | 2020.04.26 |
---|---|
[백준 c++] 14501번 : 퇴사 (2) | 2020.04.26 |
[백준 c++] 14499번 : 주사위 굴리기 (0) | 2020.04.25 |
[백준 c++] 13458번 : 시험 감독 (0) | 2020.04.25 |
[백준 c++] 3190번 : 뱀 (0) | 2020.04.25 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- ios
- Collection
- c++
- 코딩테스트
- 자료구조
- 깊이우선탐색
- 구슬탈출
- 이진트리
- 시뮬레이션
- Swift
- 백준
- Programmers
- dfs
- 알고리즘
- 삼성역량테스트
- 스위프트
- SummerCoding
- ec2
- 호제법
- BFS
- Xcode
- dp
- 컬렉션
- datastructure
- aws
- 서머코딩
- count
- algorithm
- isempty
- 프로그래머스
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함