BOJ 문제 링크: https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
정사각형 4개를 이어 붙인 폴리오미노를 테트로미노라 한다.
테트로미노를 90도 회전, 대칭 해서 만들 수 있는 모든 모양의 블럭들중 하나를 각 칸마다 숫자가 적혀있는 N*M종이위에 놓는다.
이때 블럭으로 덮은 칸들의 수들의 합이 최대가 되는 경우를 구하는 문제이다.
먼저 필요한것은 테트로미노로 만들 수 있는 모든 블럭들의 경우들을 구하는 것이고, 총 19개의 경우가 있다는걸 알 수 있다.
가장 직관적인 방법은 이 19개의 블럭들을 하나하나 좌표로 표현해서 푸는 방법이다.
다른 방법으로는 재귀를 이용해 블럭을 한칸씩 4가지 방향으로 4번 확장시키고 나머지 예외를 처리하는 방법이 있다.
첫번째 방법은 블럭들의 좌표를 하나하나 좌표로 표현한다는게 너무 하드코딩 아닌가 생각이들 수 있다.
하지만 두번째 방법으로 풀더라도 블럭들의 모든 경우를 생각해야 하며 해당 알고리즘으로 커버하지 못하는 모양( ㅗ, ㅓ, ㅏ, ㅜ)
들을 예외처리 해야한다는 부담이 있기 때문에 첫번째 방법으로 풀었다.
코드 원본: https://github.com/sbl133/BOJ/blob/main/%2314500.cpp
GitHub - sbl133/BOJ
Contribute to sbl133/BOJ development by creating an account on GitHub.
github.com
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!
'Algorithm > BOJ' 카테고리의 다른 글
| [BOJ] 백준 17836번 공주님을 구해라! c++ (0) | 2021.10.12 |
|---|---|
| [BOJ] 백준 3190번 뱀 c++ (0) | 2021.10.10 |
| [BOJ] 백준 11054번 가장 긴 바이토닉 부분 수열 (0) | 2021.10.04 |
| [BOJ] 백준 14698번 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) c++ (0) | 2021.10.01 |
| [BOJ] 백준 17828번 문자열 화폐 c++ (0) | 2021.09.29 |