알고리즘 - 백준 - 1034 - 램프 - JAVA

김성일·2024년 10월 22일

골드 백준 알고리즘 애드혹

알고리즘

목록 보기

19/23

문제 바로가기

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

문제 소개 및 재정의

아 정형적인 문제가 아니다.
너무 어렵다.
그래서 다른 사람의 해설을 참고했다.
https://kosaf04pyh.tistory.com/304
여기서 얻은 힌트는 패턴이 같은것끼리만 같은 결과로 묶을수 있다는 것이었다.
힌트를 얻은 후에는 자력으로 해결했다.

문제 패턴

정형화된 문제가 아니라 패턴은 없다.

어떻게 풀까? - 애드혹

포인트

행단위로 뜯어서 이진수로 만든다.
이진수를 십진수로 변환한다.
최대 50bit의 이진수가 나올수 있으므로 long타입을 사용한다.
변환한 십진수는 id로 사용된다.

id가 같다면 같은 패턴이다.
다시 말해서 스위치를 하나라도 작동시켰을때의 결과가 서로 같다.
id가 다르다면 다른 패턴이다.
스위치를 하나라도 작동시켰을때의 결과가 서로 다르다.

어떤 id가 켜질수 있는지 확인하는 로직은 다음과 같다.

켜야되는 스위치의 개수(realK=>r)가 K개보다 크다. => 못킨다.

켜야되는 스위치의 개수(realK=>r)가 K개보다 크다. => 일단 다 킨 상태를 만들수 있다.

근데 K번의 기회를 모두 사용해야만함.

k-r=s(surplus) 잉여회수로 정한다.

s가 짝수여야지만 행의 모든 곳이 켜진다. => 킬수 있다.

s가 홀수면 다 켜진 상태에서 꼭 한 열을 꺼야한다. => 고로 킬수 없다.

중복수가 많은것부터 가능한지 확인하고, 가능하다면 그 중복수를 제출하면된다.
근데 최대 50번만 반복하면돼서 그냥 전부다 가능한지 확인하고, 가능할때 중복수의 최대값을 관리했다.

id값을 key로 두가지 맵에 매핑한다.
id의 중복개수를 세는 맵에 매핑하고.
그 id가 켜지기 위해서 몇개의 스위치를 켜야하는지도 맵에 매핑한다.
key를 하나씩 꺼내보면서 킬수있는지 확인한다.
킬수있으면 그 id랑 같은 패턴의 개수를 최대값과 비교해서 갱신한다.

코드

package study.week14;

import java.io.*;
import java.util.*;

public class BOJ_1034_램프 {
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	// 세팅
	static int N;
	static int M;
	static int K;
	static Map<Long, Integer> countMap = new HashMap<>(); 	// long값으로 해싱하고 같은 값이 들어오면 값 +1
	static Map<Long, Integer> turnOnMap = new HashMap<>();	// long값으로 해싱한 ID에 몇개 켜야되는지 저장하기.
	static int maxi = 0;
	// 메소드
	//// id로 변환
	static long hash(char[] cArr) {
		long sum=0;
		for (int i = 0; i < cArr.length; i++) {
			if(cArr[i]=='1')
				sum += (long) Math.pow(2, i);
		}
//		System.out.println(sum);
		return sum;
	}
	//// 키는데 필요한 스위치 개수
	static int turnOn(char[] cArr) {
		int sum=0;
		for (int i = 0; i < cArr.length; i++) {
			if(cArr[i]=='0')
				sum++; // 켜야 하는 전구의 개수.
		}
//		System.out.println(sum);
		return sum;
	}
	//// 이 id가 켜질수 있는지 체크
	static boolean isOK(int r) {
		if(r>K) 		// 켜야되는 스위치를 다 못킴.
			return false;
		int s = K-r; 	// 잉여 스위치 구함.
		if(s%2==0) 		// 잉여가 짝수면 소멸가능. 킬수있음.
			return true;
		else			// 잉여가 홀수면 소멸 불가능. 못킴.
			return false;
	}
	// 메인
	public static void main(String[] args) throws Exception{
		// 입력
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		for (int i = 0; i < N; i++) {
			char[] cArr = input.readLine().toCharArray(); 	// for문 돌리기 편하게 문자열을 char[]로 받음
			long id = hash(cArr);							// 이진수를 십진수로 바꿔서 id 만듬. 50비트라서 long으로 받음
			int turnOn = turnOn(cArr);						// 켜야되는 전구의 개수 => 켜야되는 스위치의 개수를 저장
			turnOnMap.put(id, turnOn);						// id 값에 켜야되는 스위치의 개수 매핑
			if(countMap.containsKey(id)) {					// id 값을 매핑한적 있으면, 그 값에 +1 // 연습. containsKey() 연습 // 디버깅 포인트  2. countMap.containsKey(cArr) 이따구로 적었네.
				int count = countMap.get(id);				// 디버깅 포인트  2. countMap.containsKey(cArr) 이따구로 적었네. 정신없다 정신없어.
				countMap.put(id, count+1);
			} else {										// id 값을 매핑한적 없으면, 1 저장.
				countMap.put(id, 1);
			}
		}
		K = Integer.parseInt(input.readLine());				// 디버깅 포인트 1. 변수 입력을 안받았음 ㅋㅋ;;
		
		// 세팅
		// 작업
		Set<Long> keySet = countMap.keySet();				// 연습. keySet() 연습.
//		for (long key: keySet) {
////			System.out.println(key+" : "+countMap.get(key));
//			int r = turnOnMap.get(key);
//			boolean result = isOK(r);						// 이 패턴이 킬수있는건지 판단.
////			System.out.println(r+" : "+result);
//			if(result)										// 이 패턴을 킬수 있다면?
//				maxi = Math.max(maxi, countMap.get(key));	// 이 패턴의 개수를 최대값과 비교해서 갱신한다.
//		}
		
		Long[] keys = keySet.toArray(new Long[0]);			// 연습. 배열로 만드는 연습.
//		System.out.println(Arrays.toString(keys));
		for (int i = 0; i < keys.length; i++) {
			int r = turnOnMap.get(keys[i]);
			boolean result = isOK(r);						// 이 패턴이 킬수있는건지 판단.
			if(result)										// 이 패턴을 킬수 있다면?
				maxi = Math.max(maxi, countMap.get(keys[i]));	// 이 패턴의 개수를 최대값과 비교해서 갱신한다.
		}
		// 출력
		System.out.println(maxi);
		
	}// 메인 종료

}