백준 1034 - 램프(java)

www.acmicpc.net/problem/10www.acmicpc.net/problem/1034

1034번: 램프

1. 유형

그리디, 브루트포스

 

2. 풀이

 

처음 풀이는 M의 길이만큼 뒤집을 수 있는 조합을 만들어서 

 

전부 구하려고 했다.

 

하지만 그렇게 되면 2^M 즉, 최대 2^50가지의 경우가 나오기 때문에 시간 초과가 걸린다.

 

때문에 다른 접근 방식이 필요하다.

 

풀이2

위와 같은 예시에서 정답은 3이다

 

위와 같은 예시에서는 정답이 0 이다.

이걸로 K값의 홀짝 여부를 파악 해야한다.

 

범위

K의 범위는 1000까지 이다. 하지만 M의 범위는 50까지다.

 

1열 스위치를 2번 누를 경우, 원상태로 바뀐다.

 

이 조건을 활용하여 스위치는 최대 50번까지만 누를 수가 있다. 

 

K가 50 초과이면 K를 50으로 두고 문제를 푼다.

 

스위치 누르기

K가 홀수일때, 내가 선택한 행의 0 갯수도 홀수 이고, (0갯수 <= K ) 조건도 만족해야한다

위의 예시 처럼... (2 <= K), 그러면 행 하나를 전부 1로 만드는 것이 가능

 

문제의 정답은 최대값을 구하는 것이기 때문에 똑같은 패턴이 가장 많이 나오는 것을 찾으면 된다.

 

예시에서는 1 0 1 0 이 3번 나왔기 때문에 정답은 3이 된다.

 

 

• 구현기능
  • K가 홀수인지 짝수인지 파악
  • 각 행 마다 0개수 파악
  • 0의 개수와 K의 홀짝 여부가 같은지 파악
  • 같은 패턴이 몇개인지 찾음, 그중 최대값이 답
• 자료구조
  • 딱히 없음

3. 코드

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

public class Main {
	static int N, M, K, arr[], max = 0;
	static String str[];
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		M = Integer.valueOf(st.nextToken());
		str = new String[N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			str[i] = st.nextToken();
		}
		st = new StringTokenizer(in.readLine());
		K = Integer.valueOf(st.nextToken());
		int oddEven=K%2;
		if(K>50) {
			K=50;
		}
		int max =0;
		int idx=-1;
		for(int i=0; i<N; i++) {
			int zeroNum=0;
			String tmp = str[i];
			//0갯수 파악
			for(int j=0; j<M; j++) {
				if(tmp.charAt(j) == '0')
					zeroNum++;
			}
			//짝수 홀수  맞아야함
			if(zeroNum%2 != oddEven) {
				continue;
			}
			int patern =1;
			//같은 패턴이 몇개인지 파악
			for(int k=0; k<N; k++) {
				if(k!=i && tmp.equals(str[k])) {
					patern++;
				}
			}
			//0갯수가 K개 이하여야함
			if(zeroNum<=K && patern > max) {
				max = patern;
				idx = i;
			}
		}
		if(idx!=-1) {
			System.out.println(max);
		}else {
			System.out.println(0);
		}
	}
}

4. 느낀점

풀기 전에 먼저 시간복잡도를 생각하는 습관기르기