출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=292&sca=50
Input
5 6
.*....
.*****
.*....
*****.
.*....
Output
3
가로로만 막대를 놓는 경우
그리디 알고리즘으로 쉽게 막대의 개수를 구할 수 있습니다.
앞에서부터 차례대로 아직 덮지 않은 '*'를 덮어 나가면 됩니다.
이 때 가능한 오른쪽으로 덮을 수 있는 '*'을 최대한 함께 덮어야 합니다.
행의 수가 5개 미만이 경우
열의 최대 길이는 최대 10이므로 ***** 막대기를 놓는 경우는 0~2개 입니다.
중간에 하나의 점만 포함되어도 2개의 막대기를 가로로 놓을 수 없습니다.
ex) "*****.****" / "********.*"
한쪽으로 몰려서 5개 이상인 경우는 가능하다.
ex) "******...."
각 행에 대하여 '*' = 1 / '.' = 0을 놓고 prefix sum을 구해보자.
가로로 놓을 수 없는 행이 한개라도 있는 경우 100(불가능을 의미)을 반환하고
놓을 수 있다면 최소 개수 반환
*****가 연속적으로 존재한다면
j의 값을 막대의 마지막 위치로 넘어갑니다. (j = k - 1;)
col[i][j] = i행의 prefix-sum이 저장되어 있다.
used[j]는 j번 열에 세로 막대를 놓는 경우 1 / 그렇지 않은 경우 0이 저장된다.
분석
① i행 j열에 '*'가 있고 세로 막대에 포함되지 않는다면
② i행 j열 또는 j열보다 앞선 위치에서부터 가로로 놓아본다.
③ 놓은 개수 증가시키고 j를 가로 막대의 마지막 위치로 이동
④ j의 위치가 막대의 마지막 위치가 될 수 없는 경우 다음 행을 살펴볼 필요없이 불가능(100) 반환
→ i가 N번, j와 k가 함께 M번 이므로 O(N * M)
[행의 수가 5개인 경우]
j번 열에 *의 개수가 5개 이어야만 세로로 놓을 수 있다. → row[j]에 누적
row[j]가 모두 5라고 할 때, 각 열에 대하여 세로 막대를 놓거나 안 놓거나 경우의 수를 둘 수있습니다.
N이 5인 경우 세로로 놓을 수 잇는 막대는 최대 10개
10개를 놓을 수 있는 경우의 수는 최대 210 = 1024가지이다.
세로로 놓을 수 있는 모든 경우(= 1024)에 대하여 각각의 calc() 함수를 호출합니다.
→ O(2M * N * M)
※ 비트 연산을 이용한 풀이
#include <stdio.h>
int N, M, ans = 100;
int row[12], col[6][12], used[12];
int calc() {
int i, j, k, cnt = 0;
for (i = 1; i <= N; ++i){
for (j = 1; j <= M; ++j) if (col[i][j] && !used[j]) {
for (k = j; k <= M && k < j + 5 && col[i][k]; ++k);
cnt++; j = k - 1;
if (col[i][j] < 5) return 100;
}
}
return cnt;
}
void dfs(int j, int cnt) {
if (j > M) {
int tsum = cnt + calc();
if (tsum < ans) ans = tsum;
return;
}
dfs(j + 1, cnt);
if (row[j] < 5) return;
used[j] = 1;
dfs(j + 1, cnt + 1);
used[j] = 0;
}
int main() {
// freopen("input.txt", "r", stdin);
scanf("%d %d", &N, &M);
int i, j;
char c;
for (i = 1; i <= N; ++i) {
for (j = 1; j <= M; ++j) {
scanf(" %c", &c);
if (c == '.') continue;
row[j]++;
col[i][j] = col[i][j - 1] + 1;
}
}
dfs(1, 0);
printf("%d\n", ans == 100 ? -1 : ans);
}
'PS 문제 풀이 > Jungol' 카테고리의 다른 글
[Jungol] 정올 1681 해밀턴 순환 회로 (0) | 2021.02.27 |
---|---|
[Jungol] 정올 1013 Fivestar (Bitwise) (0) | 2021.02.27 |
[Jungol] 정올 2270 여객선(Cruise) (0) | 2021.02.27 |
[Jungol] 정올 1929 책꽂이 만들기 (0) | 2021.02.27 |
[Jungol] 정올 1318 못생긴 수 (0) | 2021.02.27 |
댓글