비트마스킹2 [백준 1285] 동전 뒤집기 \( N \leq 20\)이므로 \(2^N\) 또는 그에 준하는 풀이를 생각해볼 만하다. 가로 \(N\)개의 줄, 세로 \(N\)개 줄 중 무엇을 뒤집을 것인지 생각하는 문제이므로 존재할 수 있는 선택의 개수는 \(2^{2N}\)이다. 그중에서 가로줄과 세로줄 중 하나가 몇 번 줄을 뒤집을지 그 상태가 이미 정해졌다면(편의상 세로줄이라 하겠다), 가로줄에 H가 더 많으면 가만히 놔두는 것을 선택하고 T가 더 많으면 뒤집는 것을 선택하는 그리디 알고리즘을 생각할 수 있다. 이것이 성립하는 이유는 세로줄이 이미 선택된 이상 모든 가로줄은 서로 영향을 주지 않는 독립이므로 순간의 최적 선택이 전체 최적 선택을 담보하기 때문이다. 한 번 그리디 알고리즘을 시행할 때마다 전체 셀 개수인 \(O(N^2)\)의 시간.. 2024. 1. 10. [백준 18292] NM과 K (2) (Platinum IV) https://www.acmicpc.net/problem/18292 18292번: NM과 K (2) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 1014번 컨닝과 비슷한 Bitmask DP 문제다. 티어도 컨닝과 똑같은 티어가 찍혔다. 3차원 dp로 해결 가능한데 for문은 4중첩으로 돌려야 한다. dp[i][j_bits][k]를 다음과 같이 정의하자 : i번째 행까지 봤고, i번째 행에서 선택을 j_bits와 같이 했으며, 0..i행 통틀어서 k개의 선택을 했을 때, 점수의 최댓값 그 다음 dp[i]에서 dp[i+1]로 가는 .. 2023. 1. 29. 이전 1 다음
