글 읽기 - DP를 알고리즘 분류에 추가할 수 있을 것 같습니다.

이 풀이는 일종의 DP를 이용한 풀이입니다. 총 3단계로 문제를 나눕니다.

1. 8*8크기의 판의 칠해야 하는 칸의 수가 가장 적은 경우를 구하는 것이 목표입니다.

2. 각 판은 총 8개의 가로줄로 이뤄집니다. 즉, 판에 칠하는 칸의 수는 8개의 가로줄 각각의 칠해야 하는 칸의 합입니다.

3. 가로줄은 8개의 칸으로 이루어졌으며, 가로줄은 8개의 칸 중 칠해야 하는 칸과 아닌 칸의 합으로 이루어집니다.

즉, 각 칸에 대해 현재 칸의 값, 현재 칸이 마지막이 되는 줄의 칸의 합, 그 줄이 마지막 줄이 되는 판의 줄의 합이 있으면 풀 수 있습니다.

현재 알고리즘의 분류는 solved.ac 에서 유저들의 투표로 이루어집니다. 분류가 추가되기를 원하신다면 거기서 투표를 하거나, solved.ac의 Slack에서 논의를 하는 방법이 있습니다.

개인적으로는 이 문제는 일반적으로 DP라고 부르는 형태라기보다는 그냥 모든 경우의 수를 해보는 브루트포스에 가깝다고 생각합니다. 어떤 특정한 '상태'들과의 연결 고리를 고려할 필요가 없이 모든 경우를 독립적으로 시뮬레이션만 해보면 되기 때문입니다.

가능성만으로 분류를 구분하는 것이 아니었군요. 답변 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge