[백준 / BOJ] 1034 램프

문제

출처 : www.acmicpc.net/problem/1034

1034번: 램프

N*M배열의 각 칸마다 램프가 들어있고, 한 행이 전부 켜져있을때, 그 행이 켜져있다고 말한다.

램프는 껏다킬수있는데, 한 램프를 선택해서 램프를 키면, 그 램프가 들어있는 행의 모든 열이 다 켜진다.

N*M배열의 크기와 각 칸에 들어있는 램프의 상태가 주어졌을때, K번 램프를 껏다킨후 켜져있는 행의 최댓값을 구하는 문제다.

 

 

풀이

완전탐색으로 접근하면 시간초과가 날거같아서 ((1000 * 50)*1000번 반복함..) 어떻게 해야할까 생각하다 감이안잡혀서 알고리즘 분류를 봤는데 완전탐색이였다

처음에는 단순하게 백트래킹을 사용해서 완전탐색으로 접근했고 시간초과가 나왔다. (한 행씩 껏다키면서 모든 경우를 다 봐줌)

 

(시간초과가 나오고 반복횟수를 계산해보니 각 칸을 껏다키는 연산을 제외하고도 50000의 1000승 반복한다..)

시간초과 소스코드

//

//  main.cpp

//  1034 램프

//

//  Created by 이준영 on 19/08/2020.

//  Copyright © 2020 이준영. All rights reserved.

//



#include <iostream>

#include <string>

#include <algorithm>



using namespace std;



int N, M, K, max_num = 0;

int arr[55][55];



void swi(int idx){

    for(int i = 1; i <= N; i++){

        if(arr[i][idx] == 1){

            arr[i][idx] = 0;

            continue;

        }

        arr[i][idx] = 1;

    }

    return;

}



void go(int cnt){

    if(cnt == 0){

        int num = 0;

        for(int i = 1; i <= N; i++){

            int c = 0;

            for(int j = 1; j <= M; j++){

                if(arr[i][j] == 0){

                    c = 1;

                    break;

                }

            }

            if(c == 0){

                num++;

            }

        }

        max_num = max(max_num,num);

        return;

    }

    for(int i = 1; i <= M; i++){

        swi(i);

        go(cnt - 1);

        swi(i);

    }

}



int main(int argc, const char * argv[]) {

    ios::sync_with_stdio();

    cin.tie(NULL);

    cout.tie(NULL);

    cin >> N >> M;

    for(int i = 1; i <= N; i++){

        string str;

        cin >> str;

        for(int j = 0; j < str.size(); j++){

            arr[i][j+1] = (int)str[j] - 48;

        }

    }

    cin >> K;

    go(K);

    cout << max_num << "\n";

    return 0;

}

 

시간을 줄이기 위해 열을 기준으로 반복해줬다.

열을 기준으로 K번 눌렀을때, 한 행을 전부 킬수있는지 확인한다.

K번 눌러서 한행을 전부 키기위해선,

 

1. 한행에 꺼져있는 램프의 갯수가 K와 같다.

2. 한행에 꺼져있는 램프의 수가 K보다 작을때, K - 꺼진 램프의 수 가 2의 배수다. 

 

이 두가지 조건중 한가지를 만족하면 된다.

1번은 당연한거니 2번을 설명하자면, 

한 행을 전부 켯을때 램프를 켤수있는 기회(K)가 홀수번 남아있다면, 한 행을 온전히 킬수없다. 그 이유는,

 

1. 켜져있는 램프를 홀수번 누르면 램프는 무조건 꺼진다.

2. 켜져있는 램프를 짝수번 누르면 램프는 무조건 켜진다.

 

또한, 홀수번 남았을때, 램프를 나눠서 누르는 경우또한 전부 켤수없는데, 홀수를 짝수의 합으로 나타낼수없기 때문이다..

(홀수는 짝수 + 1 임으로.. 무조건 1이 남게됨)

따라서 여러가지 램프를 나눠서 누른다고해도 무조건 한 램프는 꺼진다...

 

이미 처음에 한행을 전부 켜줬으니 남아있는 K가 홀수라면 한 램프는 무조건 꺼지게된다.

 

위에있는 조건을 만족하면서 열의 갯수만큼 반복시키고, 한번 램프를 킬때마다 만들어진 켜져있는 행의 수를 구해준다.

(램프를 킨다음 다시 원상태로 돌려놓는걸 잊지말자)

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1034%20%EB%9E%A8%ED%94%84/main.cpp

devxb/JJUNalgo