반응형
문제 출처 :
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,0 }; int dx[4] = { 0,-1,0,1 }; 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 ((1 <= ny && ny <= n) && (1 <= nx && nx <= n)) t[ny][nx] == 1 ? t[ny][nx] = 0 : t[ny][nx] = 1; } t[y][x] == 1 ? t[y][x] = 0 : 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 ? -1 : 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 |