본문 바로가기
PS 문제 풀이/Jungol

[Jungol] 정올 1013 Fivestar

by 까망 하르방 2021. 2. 27.
반응형

출처: 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);
       
}
반응형

댓글