oVeron

1.격자판의 각 칸을 왼쪽 위에서부터 \(0, 1, 2, ... , N*M-1\)이라 하자. 012...                   ...\(K\)xxxxxxx                \(N*M-1\)  \(K\)번 칸 이전은 전부 격자를 채웠다고 가정하고 \(K\)번 칸에 주목해보자. 저 칸에 격자를 놓는 경우는 3가지다. 1. 이미 \(K\)번 격자가 채워져 있어서 격자를 놓을 수 없다.2. 격자를 가로로 놓는다.3. 격자를 세로로 놓는다. 위 세 경우 모두 'x'친 구간에만 영향을 받는다. 따라서 저 'x'친 구간을 하나의 집합으로 관리하며, 집합의 상태에 따라 앞으로 격자를 놓는 경우의 수가 얼마인지 계산해 나가면 문제를 해결할 수 있다. \(K\)번 칸 이후에 격자를 놓을 수 있는 경우..

알고리즘/baekjoon 2024. 6. 28. 19:32