[백준] 1034번 : 램프 Gold4(골드4) - JAVA[자바]

[Gold IV] 램프 - 1034

문제 링크

성능 요약

메모리: 11632 KB, 시간: 64 ms

분류

애드 혹, 브루트포스 알고리즘

제출 일자

2024년 6월 1일 00:55:34

문제 설명

지민이는 각 칸마다 (1×1크기의 정사각형) 램프가 들어있는 직사각형 모양의 탁자를 샀다. 모든 램프는 켜져있거나 꺼져있다. 각 열의 아래에는 스위치가 하나씩 달려있는데, 이 스위치를 누를 때마다 그 열에 있는 램프의 상태가 바뀐다. 켜져있는 램프는 꺼지고, 꺼져있는 램프는 켜진다)

만약 어떤 행에 있는 램프가 모두 켜져있을 때, 그 행이 켜져있다고 말한다. 지민이는 스위치를 K번 누를 것이다. 서로다른 스위치 K개를 누르지 않아도 된다. 지민이는 스위치를 K번 눌러서 켜져있는 행을 최대로 하려고 한다.

지민이의 탁자에 있는 램프의 상태와 K가 주어졌을 때, 스위치를 K번 누른 후에 켜져있는 행의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져있는 상태이다. 마지막 줄에는 K가 주어진다. K는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

접근 방법

* 접근 방법: 브루트포스, 애드 혹
* 1. K의 값이 짝수개라면 0의 개수가 짝수인 곳의 행을 전부 1로 만들 수 있고
* 2. 홀수라면 0의 개수가 홀수인 곳의 행을 전부 1로 만들 수 있다.
* 3. 그 말은 즉, 각 열의 존재하는 0의 개수가 K개를 초과하지 않는다면 커버 가능한 것이다.
* 4. 동일하게 등장하는 값들을 세주면서 최대값을 갱신해주면 됨

문제를 잘 읽어보면 처리하기 쉬운 문제 

 

import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;

/**
 * 문제: Main_1034_램프_골드4
 * 메모리:11632KB
 * 시간: 64ms
 * 접근 방법: 브루트포스, 애드 혹
 * 1. K의 값이 짝수개라면 0의 개수가 짝수인 곳의 행을 전부 1로 만들 수 있고
 * 2. 홀수라면 0의 개수가 홀수인 곳의 행을 전부 1로 만들 수 있다.
 * 3. 그 말은 즉, 각 열의 존재하는 0의 개수가 K개를 초과하지 않는다면 커버 가능한 것이다.
 * 4. 동일하게 등장하는 값들을 세주면서 최대값을 갱신해주면 됨
 */
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 answer = 0;

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

        // Input
        String[] inputs = new String[N];
        for (int i = 0; i < N; i++) {
            inputs[i] = br.readLine();
        }// Input End

        HashMap<String, Integer> map = new HashMap<>();
        int K = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            int count = 0;
            for (int j = 0; j < M; j++) {
                // 0의 개수를 카운트
                if (inputs[i].charAt(j) == '0') {
                    count++;
                }
            }
            /*
            0의 개수가 K보다 적고(커버 가능한 0의 개수) && count 와 K가 같은 수 일때(같은 짝수, 같은 홀수 일때)
            answer 값을 갱신
            */
            if (count <= K && count % 2 == K % 2) {
                map.put(inputs[i], map.getOrDefault(inputs[i], 0) + 1);
                if (map.get(inputs[i]) > answer) {
                    answer = map.get(inputs[i]);
                }
            }
        }
        System.out.println(answer);
    }
}