[백준 알고리즘] 22251번 자바(Java) 빌런 호석

문제

치르보기 빌딩은 1층부터 N층까지 이용이 가능한 엘리베이터가 있다. 엘리베이터의 층수를 보여주는 디스플레이에는 K 자리의 수가 보인다. 수는 0으로 시작할 수도 있다. 0부터 9까지의 각 숫자가 디스플레이에 보이는 방식은 아래와 같다. 각 숫자는 7개의 표시등 중의 일부에 불이 들어오면서 표현된다.

 

예를 들어 K=4인 경우에 1680층과 501층은 아래와 같이 보인다.

  

빌런 호석은 치르보기 빌딩의 엘리베이터 디스플레이의 LED 중에서 최소 1개, 최대 P개를 반전시킬 계획을 세우고 있다. 반전이란 켜진 부분은 끄고, 꺼진 부분은 켜는 것을 의미한다. 예를 들어 숫자 1을 2로 바꾸려면 총 5개의 LED를 반전시켜야 한다. 또한 반전 이후에 디스플레이에 올바른 수가 보여지면서 1 이상 N 이하가 되도록 바꿔서 사람들을 헷갈리게 할 예정이다. 치르보기를 사랑하는 모임의 회원인 당신은 호석 빌런의 행동을 미리 파악해서 혼쭐을 내주고자 한다. 현재 엘리베이터가 실제로는 X층에 멈춰있을 때, 호석이가 반전시킬 LED를 고를 수 있는 경우의 수를 계산해보자.

 

입력

 N, K, P, X 가 공백으로 구분되어 첫째 줄에 주어진다.

출력

호석 빌런이 엘리베이터 LED를 올바르게 반전시킬 수 있는 경우의 수를 계산해보자.

 

풀이

• 시간복잡도, 메모리
  • 최대층까지 각 층을 한번씩 확인하면 되므로 O(N) 모든 조건에 대입 시킨다고 해도 10의 6승이다
  • 2단 배열 사용하는 부분도 초반에 led변환개수 체크용 말고는 없으므로 크게 신경쓸부분은 없다 만일 100만의 숫자를 돌때 메서드 안에서 배열을 사용했다면 문제였겠지만 새로운 int 변수 선언 말고는 없다
• 풀이과정
  • 기존 0~9기준 0~9를 만드는데 필요한 LED변환 개수를 기록한 배열을 만들어준다.
  • 가능한 자리수 K를 토대로 맨앞의 자리수부터 0~9번호로 계속 뻗어나가게 한다
    • 뻗어나가면서 LED변환 개수 표시한 arr을 토대로 해당 층의 LED변환 개수를 체크해준다
    • 이를 토대로 메서드를 만들면 houskCanDoIt(누적변환개수, 현재 체크하고 있는 자리수)
  • 다음 조건을 만족해야한다
    • 0, 000과 같이 0으로 끝나면 안되므로 연달아 0이존재하는지 파악하는 boolean형 타입을 파라미터로 넣어준다
    • 최대층을 고려해야하므로 앞자리수가 최대 층이라면 다음 층도 그 제한이 걸려있어야한다, 따라서 전 자릿수가 최대층이 계속되었는지 판단하는 boolean형 파라미터를 넣어준다
    • 변화된 메서드: hosukCanDoIt(int cnt, int index, boolean maxTrue, boolean zeroTrue)

 

예제 입력 예시

48 2 5 35

 

예제 출력 예시

30

 

소스코드

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

//22251번 빌런 호석

public class P22251 {
    private static final int[][] arr = {
            {0, 4, 3, 3, 4, 3, 2, 3, 1, 2},
            {4, 0, 5, 3, 2, 5, 6, 1, 5, 4},
            {3, 5, 0, 2, 5, 4, 3, 4, 2, 3},
            {3, 3, 2, 0, 3, 2, 3, 2, 2, 1},
            {4, 2, 5, 3, 0, 3, 4, 3, 3, 2},
            {3, 5, 4, 2, 3, 0, 1, 4, 2, 1},
            {2, 6, 3, 3, 4, 1, 0, 5, 1, 2},
            {3, 1, 4, 2, 3, 4, 5, 0, 4, 3},
            {1, 5, 2, 2, 3, 2, 1, 4, 0, 1},
            {2, 4, 3, 1, 2, 1, 2, 3, 1, 0}
    };

    private static char[] N;
    private static int K;
    private static int P;
    private static char[]X;
    private static char[]startCharArr;
    private static int sumCnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = st.nextToken().toCharArray(); //최대층
        K = Integer.parseInt(st.nextToken()); //자리수
        P = Integer.parseInt(st.nextToken()); //led변환 최대개수
        X = st.nextToken().toCharArray(); //현재 층

        //시작 문자열이 있어야함
        startCharArr = new char[K];
        Arrays.fill(startCharArr, '0');
        for (int i = 1; i <=X.length; i++) startCharArr[startCharArr.length-i] = X[X.length-i];

        sumCnt = 0;
        hosukCanDoIt(0, 0, true, true);
        //현재층 포함된거이므로 제외
        System.out.println(sumCnt-1);
    }

    private static void hosukCanDoIt(int cnt, int index, boolean maxTrue, boolean zeroTrue){
        if(index == K&&cnt <= P){
            sumCnt++;
            return;
        }
        else if(cnt>P) return;

        int startNum = startCharArr[index]-48;
        int maxNum = N[index]-48;
        for (int i = 0; i <10; i++) {
            //0층 체크
            if(zeroTrue&&i==0){
                if(index==K-1){}
                else if(maxTrue&&i==maxNum) hosukCanDoIt(cnt+arr[startNum][i], index+1, true, false);
                else hosukCanDoIt(cnt+arr[startNum][i],index+1,false, true);
            }
            //최대층 체크
            else if(maxTrue&&i>maxNum) return;
            else if(maxTrue&&i==maxNum) hosukCanDoIt(cnt+arr[startNum][i], index+1, true, false);
                //0층, 최대층 제외일경우
            else hosukCanDoIt(cnt+arr[startNum][i], index+1, false, false);
        }
    }
}

 

 

 

 

문제 출처

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

22251번: 빌런 호석