[Java] 백준 1034 : 램프

[문제]

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

1034번: 램프

 

[풀이 과정]

 

문제 요약 : 각 열에 달려 있는 스위치를 K번 눌러서 켜져있는 행의 개수의 최대값을 구하는 문제이다.

스위치를 누르면 그 열에 있는 램프의 상태가 바뀌게 되는데 , 켜져있는 램프는 꺼지고 꺼져있는 램프는 켜진다.

 

 

N과 M의 범위는 1부터 50 , K의 범위는 0 혹은 1~1000까지의 자연수이다.

 

 

처음에는 , 모든 경우를 전부 확인하기 위하여 하나의 열에 대해서 스위치를 누른상태와 누르지 않은 상태를 가지고 

램프의 모든 경우를 만들어 정답을 찾으려고 해보았다. 하지만 그렇게 되면 열이 최대 50개인데 2^50 의 시간복잡도를 가지기 때문에 효율적인 방법이 아니였다.

 

 열을 가지고 스위치를 눌렀을때와 누르지 않았을때의 상태를 가지고 켜져있는 행의 최대를 구하기는 어렵다 생각하여 행을 기준으로 문제를 바라보게 되었다.

 

 

 최대값을 구하기 위해서 어느 한 상황(스위치를 누르거나,,안누르거나,,)에 대하여 몇개의 행이 켜질 수 있는지 개수를 세주어야할 필요가 있었다. 하지만 경우에 수가 많기때문에 어떻게 줄일 수 있는지 생각해보았다.

 

 어짜피 행이 켜져있는 상황에서 개수를 구하는 거라면 하나의 행이 켜져있다 가정했을때 (k번으로 켜질 수 있다면) 이 상황이 결국 하나의 경우 아닌가? 라는 생각을 했다. 그렇게 되면 각 행마다 k번으로 켜질수 있는지 없는지 먼저 판단하고 , 켤 수 있는 상황이라면 그 경우에 켜지는 행의 개수를  구하면 되는거였다.

 

 

아래의 예시로 설명하자면

6 3
001
101
001
000
111
001
6

첫번째 행인 '001'을 켜져있는 행으로 만들 수 있다고 하였을때 램프들의 상황은 이럴것이다.

 

          <전>                                          <후>

0 0 1                                                  1 1 1
1 0 1                                                  0 1 1
0 0 1                                                  1 1 1
0 0 0                                                  1 1 0
1 1 1                                                  0 0 1
0 0 1                                                  1 1 1

 

이 상황에선 3개의 행이 켜진다.

 

이렇게 각 행마다 킬 수 있는 상황에서 몇개가 만들어 지는지 구하고 최대값을 비교해주면된다.

 

 

해당 행이 001 이였다면 굳이 <후> 상황처럼 만들지 않고 001의 경우가 켜질 수있다는 가정하에서 001과 같은 내용을 가진 행의 개수를 찾아주면된다.

 

[행이 켜질 수 있는 경우]

 

하나의 행을  켤 수 있다는 가정을 했으니까 그렇게 만들기 위해 0일때 스위치를 반드시 눌러야한다.

따라서 스위치를 누르는 횟수는 0의 개수가 된다.

 

그렇다면 행이 켜질 수 있는 경우는 어떠한 경우일까?

 

1. 스위치를 누른  횟수가 K보다 크면 안된다. (즉 스위치를 누른 횟수가 k와 같거나 작아야한다)

 

=> 당연한 얘기이다. 눌러야하는 횟수를  정해주었는데 그것보다 더 눌러야하는 상황이라면 안될것이다.

 

2. 만약 스위치를 누른 횟수가  k 보다 작았을때는 k- 누른횟수 = 남은 누를 수 있는 횟수가 반드시 짝수여야만한다.

 

=> a번 눌러서 행을 킬 수 있었다고 해보자. 하지만 k-a 만큼 우리는 스위치를 더 눌러줘야한다.  처음 램프가 0이였을때

한번 누르면 1이될꺼고 다시 누르면 원상태인 0으로 된다. 따라서 두번을 누르면 원래 상태로 돌아간다는 것이다. 

따라서 남은 횟수가 짝수번이여야만 행을 킬 수 있는 상태를 즉 a번 눌렀을때 의 상황과 같게 유지할 수 있다.

 

[리뷰]

 두번의 과정을 거쳐서 코드를 수정하였는데 처음에는 행이 켜질 수 있는 상황이면 그 상황에 맞게 램프값을 수정해서 행이 모두 1인지를 가지고 행의 개수를 세주었는데 그럴필요가 없었다.  그 행이 켜진다 하면 그 행과 똑같이 생긴 행들만 모두 1값을 가지고 있을거기 때문이다. 따라서 같은 문자열인지만 판단해주면 되는 문제였다.

 

[전체 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{


    public static void main(String[] args)  throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());


       int N = Integer.parseInt(st.nextToken()); //행
       int M = Integer.parseInt(st.nextToken()); //열

        
        int [] offCount = new int[N]; // 그 행에 몇의 램프가 꺼져있는지 저장할 배열 ->즉 스위치를 눌러야하는 횟수
        String [] line = new String[N]; // 그 행의 램프 상태 => ex )'1010110'
        
        for(int i = 0 ; i < N ; i++){
            String s = br.readLine();
            int zero = 0 ; // 꺼져있는 램프 개수
            for(int j = 0 ; j < M ; j++){
                if(s.charAt(j)=='0'){ //램프가 꺼져있다면
                   zero++;
                }
            }
            //행에 몇개의 램프가 꺼져있는지에 대해 저장한다.
            offCount [i]=zero;
            //해당 행의 문자열을 저장한다.
            //그 이유는 밑에 과정에서 한 행을 완성된 행(모든 램프가 켜져있는)으로 만들 수 있었을때 다른 행들이 현재 행과 똑같은 형태인지 파악하기 위함이다. -> 똑같다면 그 행은 완벽한 행으로 만들 수 있기때문
            line[i]=s;
        }

      int  K = Integer.parseInt(br.readLine()); // 스위치를 눌러야 하는 횟수
        
        int max = 0; //최소의 경우는 0
        
        /* 하나의 행에 대하여 켜질 수 행이 될 수 있다면 다른 행들중에서 같은 경우가 있는지 세어준다. -> 같은 행들도 켜져있는 행일 수 밖에 없기때문 */
         for(int i = 0 ; i < N; i++){

             //첫번째로 ,꺼져있는 램프의 개수 , 즉 스위치를 눌러야하는 횟수가 K보다 크면 안된다. 문제 조건에서 K번을 누르라고 했기 때문
             //두번째로 , K-offCount[i] = 더 눌러야 하는 횟수 , 는 짝수여야한다.  짝수여야만 현재상태와 똑같이 만들 수 있기때문이다. 두 번 누르면 원래 상태인것처럼.
             if(offCount[i]<=K&&(K-offCount[i])%2==0){

                 int equalCount = 1 ; // 현재 i은 켜져있는 행이므로 초기값은 1

                 for(int j = 0 ; j < N;j++){
                     if(i==j)continue; //자기 자신 탐색하는건 넘어간다.
                     if(line[i].equals(line[j])){ // i 행과 같은 상황의 행이 있다면 +1
                         equalCount++;
                     }
                 }

                 max=Math.max(max,equalCount); //최대값 갱신
             }


        }

        System.out.println(max); // 정답 출력

    }

}

 

[결과]