[백준/Java] 1034번 램프

🔗 문제 링크: https://www.acmicpc.net/problem/1034

🔍 해결 과정

처음에 문제를 보고 여러 개의 직사각형 보드판으로 구성되어 있는 램프들에서 구성되어 있는 열을 k번 중복 선택해서 선택된 각 열의 램프를 전부 스위칭 해주고 켜져 있는 행의 최대 개수를 구하는 방식으로 코드를 작성했지만 재귀적인 방식을 사용했을 뿐더러 새로운 램프 배열까지 만들어 그 문제로 인한 메모리 초과가 발생했었습니다. 그래서 다른 방법을 강구하느라 시간이 좀 걸린 문제였습니다.

 

다른 방식을 강구한 결과 이 문제는 재귀적인 방식을 활용하는 조합을 쓰지 않고도 더 효율적으로 문제를 해결할 수 있었습니다.

어차피 특정 열에서 스위치를 눌러서 그 열에 존재하는 전구의 상태가 전부 바뀌므로 결국 켜져 있는 행의 최대 개수는 이렇게 해석할 수도 있습니다.

k번 눌렀을 때 "켜져 있는 행"이 성립하는 패턴을 가지는 특정 행의 패턴 개수 중에서도 최대 개수

 

문제 설명에서 예제 5번을 바탕으로 자세히 설명하겠습니다. 우선 14 x 3 배열의 램프에서 특정 행이 가지는 램프 패턴 및 개수 정보는 다음과 같습니다.

"000" : 2개

"001" : 4개

"010" : 1개

"101" : 2개

"110" : 2개

"111" : 3개

여기에서 k = 6이므로 각 행의 패턴마다 k가 0의 개수보다 크다면 0을 1로 만들어주기 위해서 0의 개수만큼 차감해주고 (일단 켜져 있는 행으로 만들어줍니다.) 남아 있는 k의 개수가 짝수개가 된다면 완전한 켜져 있는 행이 성립이 되고 이 특정 행의 패턴의 개수는 켜져 있는 행의 개수 정보를 나타내주므로 이를 활용하여 켜져 있는 행의 개수의 최댓값을 갱신해주면 문제를 해결할 수 있습니다. 위 문제에서는 "001"이 켜져 있는 행이 성립이 되고  짝수개의 남아 있는 스위칭 개수를 가지고 있으므로 (k = 6에서 2개의 0을 차감한 다음 남은 개수 4개는 짝수이므로 "111"이 성립됨)켜져 있는 행의 개수의 최댓값은 4가 됩니다.

 

---

✏️ 코드

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

public class Main {

    private static final char OFF = '0';

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        String[] lamps = new String[n];

        for (int i = 0; i < n; ++i) {
            lamps[i] = br.readLine();
        }

        int k = Integer.parseInt(br.readLine());

        bw.write(Integer.toString(getResult(lamps, n, k)));
        bw.flush();
        bw.close();
    }

    private static int getResult(String[] lamps, int n, int k) {
        // lamps에서 특정 패턴들 전부 기억해두기
        Map<String, Integer> patternCountInfo = new HashMap<>();
        int maxCount = 0;

        for (int i = 0; i < n; ++i) {
            patternCountInfo.put(lamps[i], patternCountInfo.getOrDefault(lamps[i], 0) + 1);
        }

       // 이제 map에 있는 내용들을 꺼내가며 최대 개수를 구해주기
        for (Map.Entry<String, Integer> entry : patternCountInfo.entrySet()) {
            String rowPattern = entry.getKey();
            int rowCount = entry.getValue();
            int offCount = 0;

            for (char c : rowPattern.toCharArray()) {
                if (c == OFF) {
                    ++offCount;
                }
            }

	// 0을 전부 1로 만들어주고 남아 있는 횟수중 짝수개가 성립한다면
            if (k >= offCount && (k - offCount) % 2 == 0) {
                maxCount = Math.max(maxCount, rowCount);
            }
        }

        return maxCount;
    }
}