문제 링크입니다: https://www.acmicpc.net/problem/12094
12094번: 2048 (Hard)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
백준 12100번 2048 (Easy)와 달리 N이 10이기 때문에 단순 백트래킹만으로는 TLE가 발생하는 문제였습니다.
따라서 적절한 가지치기가 필요했으며 가지치기하는 기준은 다음과 같습니다.
- 보드 위에 있는 전체 블록을 한 방향으로 이동시켰을 때 블록 상태가 변하는지 여부
- 현재까지 구한 블록의 최댓값보다 다음 보드 상태에서 기대할 수 있는 블록의 최댓값이 더 클 수 있는지 여부
만약 위 두 조건의 AND 조건이 성립하지 않을 경우 재귀 호출하지 않는 방식으로 가지치기를 했습니다.
개발환경:Visual Studio 2022
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 1269번 대칭 차집합 (0) | 2024.04.24 |
|---|---|
| 백준 7795번 먹을 것인가 먹힐 것인가 (0) | 2024.04.24 |
| 백준 2776번 암기왕 (0) | 2024.04.20 |
| 백준 13144번 List of Unique Numbers (0) | 2024.04.08 |
| 백준 14469번 소가 길을 건너간 이유 3 (0) | 2024.04.08 |