[Gold V] 빌런 호석 - 22251 (Java)

 

문제 요약

치르보기 빌딩의 엘리베이터는 1층부터 N층까지 이용이 가능하고, 디스플레이에는 K 자리의 숫자가 표시됩니다. 숫자는 0으로 시작할 수 있고, 0부터 9까지의 각 숫자는 7개의 LED 표시등 중 일부가 켜져서 표현된다.
호석이는 이 엘리베이터의 LED를 최소 1개에서 최대 P개까지 반전시킬 계획을 세웠습니다. '반전'이란 켜진 LED는 끄고, 꺼진 LED는 켜는 것을 의미합니다. 그리고 반전을 통해 디스플레이에 표시되는 숫자를 1 이상 N 이하의 올바른 수로 바꿔서 사람들을 혼란스럽게 만들 예정이다.
당신은 치르보기를 사랑하는 모임의 회원으로, 호석이의 이런 행동을 미리 알아내서 막고 싶습니다. 현재 엘리베이터가 실제로 X층에 멈춰 있다고 할 때, 호석이가 반전시킬 수 있는 LED 경우의 수를 계산해 보자.

---

문제 분석

• LED 디스플레이 설정:
  • 0부터 9까지 각 숫자를 7개의 LED로 어떻게 표현하는지 DISPLAY_NUMS 2차원 배열로 설정.
• LED 스위치 횟수 계산:
  • ledSwitchCnt라는 2차원 배열을 이용해 각 숫자를 다른 숫자로 바꾸기 위한 LED 반전 횟수를 미리 계산하고 저장.
• 입력받기:
  • 빌딩의 최대 층수 N, 디스플레이의 자릿수 K, 반전 가능한 LED 개수의 최댓값 P, 그리고 현재 엘리베이터의 층수 X를 입력.
• 현재 층수 문자열화:
  • 현재 엘리베이터가 멈춰 있는 층수 X를 K 자리 문자열로 변환.
• 대상 층수 확인:
  • 1층부터 N층까지 반복하면서, 각 층수를 현재 층수 X로 바꿀 수 있는지 확인.
    
    

---

코드

package Week24;

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

public class BOJ_22251 {
    /*
        0
      1   2
        3
      4   5
        6
     */
    static final boolean[][] DISPLAY_NUMS = {
            {true, true, true, false, true, true, true}, // 0
            {false, false, true, false, false, true, false}, // 1
            {true, false, true, true, true, false, true}, // 2
            {true, false, true, true, false, true, true}, // 3
            {false, true, true, true, false, true, false}, // 4
            {true, true, false, true, false, true, true}, // 5
            {true, true, false, true, true, true, true}, // 6
            {true, false, true, false, false, true, false}, // 7
            {true, true, true, true, true, true, true}, // 8
            {true, true, true, true, false, true, true}, // 9
    };

    static int[][] ledSwitchCnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // N층까지 이용 가능한 엘리베이터
        int N = Integer.parseInt(st.nextToken());
        // 엘리베이터 디스플레이에 표시되는 숫자의 자릿수
        int K = Integer.parseInt(st.nextToken());
        // 디스플레이에서 반전시킬 수 있는 최대 LED 개수
        int P = Integer.parseInt(st.nextToken());
        // 현재 엘리베이터가 실제로 멈춰있는 층
        int X = Integer.parseInt(st.nextToken());
        // 한 수가 다른 수로 바뀔때 몇개의 LED를 변경하면 되는지 저장하는 배열
        ledSwitchCnt = new int[10][10];
        // 0부터 9까지 한번 해보기
        for(int n = 0; n < 10; n++){
            for(int m = 0; m < 10; m++){
                ledSwitchCnt[n][m] = findLedSwitchCnt(n, m);
                ledSwitchCnt[m][n] = ledSwitchCnt[n][m];
            }
        }
        // 이제 1부터 N까지 P개의 스위치 변경을 통해 수를 변경할 수 있는지 확인
        String stringN = "";
        int result = 0;
        String stringX = fitN(K, X);
        for(int n = 1; n <= N; n++){
            // 현재층은 제외
            if(n == X) continue;
            // 자리수(K) 맞춰주기
            stringN = fitN(K, n);
            // P번의 변경을 통해 X가 stringN으로 바뀔 수 있는지 확인
            result += xToStringN(stringX, stringN, P) ? 1 : 0;
        }
        System.out.println(result);
    }

    private static boolean xToStringN(String x, String stringN, int P) {
        int cnt = 0;
        for(int i = 0; i < x.length(); i++){
            int currXN = x.charAt(i) - '0';
            int currStringNN = stringN.charAt(i) - '0';
            cnt += ledSwitchCnt[currXN][currStringNN];
            if(cnt > P) return false;
        }
        return cnt <= P;
    }

    private static String fitN(int k, int n) {
        StringBuilder sb = new StringBuilder();
        String stringN = Integer.toString(n);
        for(int i = 0; i < k-stringN.length(); i++){
            sb.append("0");
        }
        sb.append(n);
        return sb.toString();
    }

    private static int findLedSwitchCnt(int n, int m){
        int result = 0;
        // n이 m이되려면 몇개의 led를 움직여야하는지 판단.
        for(int i = 0; i < DISPLAY_NUMS[0].length; i++){
            result += DISPLAY_NUMS[n][i] != DISPLAY_NUMS[m][i] ? 1 : 0;
        }
        return result;
    }
}

---

정리

개선할 점

비트마스킹으로 풀어보자.

 

---