- 다음에 다시
3. 테트로미노 14500번
- 폴리오미노
- 정사각형은 서로 겹치면 안 된다
- 도형은 모두 연결되어 있어야 한다.
- 정사각형의 변끼리 연결되어 있어야 한다. 즉 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
- 테트로미노는 정사각형 4개를 이어 붙인 것, 다음과 같이 5가지가 있다.
- NxM 종이 위에 테트로미노를 하나 놓을 때,
-
테트로미노가 놓인 칸에 쓰여있는 수들의 합을 최대로 하는 프로그램 작성하기
- 직접 다 해보는 방법 외에는 좋은 방법이 떠오르지 않는다.
- 그런데 직사각형은 가로 세로로만 따져보면 되겠지만, 문제의 주황색과 보라색, 핑크색은 90도로 회전한 방향을 다 해봐야 한다. 대칭해서 회전까지 고려해야한다.
- 이걸 다 해보는 방법이 맞는 걸까?
입력 받은 N과 M을 통해서 2차원 배열 생성 이후 값 입력 받아 Map 완성 도형은 총 5개, 경우의 수를 다 돌면 19개. 19가지의 경우의 수를 다 돌려서 가장 큰 값을 찾아본다.
풀이 동영상 내용
- 3칸의 마이너스 무한대를 우, 하에 넣는 이유는, 블록의 최대 맥스가 4x4기 때문에, 3칸만 넣어줘도 확인할 수 있다.
참고자료