ALiNew ALiNew

NM과 K(1)

• [Algo Rhythm🕺💃] BOJ 18290 - NM과 K(1)

  Algo Rhythm🕺💃/BOJ 2021. 6. 30. 17:41

  💫문제 분석 크기가 $n \times m\ (1 \le n,\ m \le 10)$인 격자판을 $g$라고 하자. $g$의 각 칸에는 정수가 하나씩 들어있는데 인접한 칸들을 제외하고 $k\ (1 \le k \le \min (4, n \times m))$개의 칸을 선택하여 각 칸에 들어있는 모든 수들을 더할 때 나올 수 있는 값들 중 최댓값을 구해야 한다. $g$의 각 칸을 하나의 vertex라고 생각해보자. 그렇다면 이 문제는 $n \times m$개의 vertex들 중에서 인접한 칸들을 제외하고 $k$개의 vertex를 선택할 때 얻을 수 있는 최댓값을 구하는 backtracking 문제로 이해할 수 있다. 🔥문제 풀이 $n \times m$개의 칸 중 $k$개의 칸을 선택할 때 한 가지 조건은 이미 선택..

  Read More