[BOJ1248] 맞춰봐

1. 문제

https://www.acmicpc.net/problem/1248

2. Note

2.1. 완전탐색 - 백트래킹

모든 경우의 수를 구하고 이를 문제의 조건과 비교하는 문제에 익숙해져서 그런지 이런 방식으로만 문제를 해결하려 했습니다. 당연하게도 시간초과를 받았습니다. 적절히 가지치기를 수행해서 문제의 조건에 어긋나는 경우를 사전에 제거하는 백트래킹으로 접근해야 했습니다.

2.2. 문제 접근 태도

문제를 풀 때, 먼저 제한 시간을 보고 입력을 어떤 알고리즘에 욱여넣을(?) 수 있는지 확인하곤 합니다. 시간복잡도 분석은 물론 중요합니다. 그러나 문제의 본질에 집중하지 않고 익숙해진 알고리즘 유형에 끼워맞춰서 시간 내에 풀 수 있는지 확인하는 나쁜 버릇이 들었습니다. 문제에 좀 더 집중해야 합니다.

3. Reference

• https://thesulks.tistory.com/42