반응형

문제 출처 :


https://www.acmicpc.net/problem/14927



알고리즘 분석 :


문제 해결에 필요한 사항

1. 그리디


전구를 끄는 방법은 다음과 같다.


1 0 0 0

0 0 0 0

....

에서

첫번째 1을 끄기 위해서는 한칸 아래의 0을 flip해주면 


0 0 0 0

1 1 0 0

....

이 될 것이다.


따라서 각 행의 전구를 끄기 위해 그다음 열의 전구를 flip해주면서 쭉 내려올 수 있다.


결국 마지막 행까지 왔을때 모든 전구가 다꺼졌다면 그 횟수중 최소가 되는 값을 찾으면 된다.


이때 첫번째 행에 대해 모든 경우의 수를 다 구성해줘본다.


예를들어 첫번째 행 번호를 1,2,3,4라 치면

1에 대해서만 flip해줄때, 1,2에 대해서 flip해줄때, ... , 1,2,3,4에 대해 flip해줄 때 모두 고려를 한 후 계산(solve함수)을 해준 후 최솟값을 구하면 답을 구할 수 있다.






소스 코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
 
using namespace std;
 
const int INF = 987654321;
int arr[20][20];
int tmp[20][20];
int chk[20];
 
int dy[4= { -1,0,1,};
int dx[4= { 0,-1,0,};
int n, ans = INF;
 
void flip(int y, int x, int t[][20])
{
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
 
        if ((<= ny && ny <= n) && (<= nx && nx <= n))
            t[ny][nx] == ? t[ny][nx] = : t[ny][nx] = 1;
    }
    t[y][x] == ? t[y][x] = : t[y][x] = 1;
}
 
int solve()
{
    int ret = 0;
    for (int i = 1; i <= n; i++)
        if (chk[i])
            flip(1, i, arr), ret++;
 
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (arr[i - 1][j])
                flip(i, j, arr), ret++;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (arr[i][j] != 0)
                return INF;
 
    return ret;
}
void func(int here)
{
    if (here == n + 1)
    {
        memcpy(tmp, arr, sizeof(tmp));
        int ret = solve();
        if (ret != INF)
            ans = min(ans, ret);
        memcpy(arr, tmp, sizeof(arr));
        return;
    }
 
    func(here + 1);
    chk[here] = true;
    func(here + 1);
    chk[here] = false;
}
 
int main()
{
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d"&arr[i][j]);
 
    func(1);
 
    return !printf("%d", ans == INF ? -: ans);
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[2792번] 보석 상자  (2) 2018.02.21
[10814번] 나이순 정렬  (0) 2018.02.20
[14925번] 목장 건설하기  (0) 2018.02.19
[11651번] 좌표 정렬하기 2  (0) 2018.02.19
[10840번] 구간 성분  (0) 2018.02.07