22251 - 빌런 호석 (Java)

 

---

 

문제

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

 

풀이

설명이 괜히 어렵게 되어있는거 같은데 대충 정리하면 n자리수의 층을 가진 엘레베이터가 있고 최대층과 현재층이 주어질 때, 현재층에서 다른 층으로 갈 수 있는 방법을 구하는 것이다. 이 때 반전이라는 개념을 사용하고, 그 횟수의 제한을 둔다.

 

우선 각 수를 배열로 나타내었다. 꺼져있는 부분은 0, 켜져있는 부분은 1로 나타냈고

그 이후에는 숫자 변형시 필요 반전 개수를 map 에 저장해뒀다.

Map<Integer, Map<Integer, Integer>> 형태로 구현하였으며

cnt = map.get(1).get(3) 라고 했을때 이는 1에서 3으로 바꿀때 필요 반전 개수가 cnt 개라는 뜻이다.

 

이렇게 구현한 다음 현재층에서 다른 층으로 이동할 수 있는지를 알아봐야 하는데,

최대층이 정해져있기때문에 1층 부터 최대층까지 반복문을 돌리면서 현재층에서 해당하는 층으로 이동 가능한지로 경우의 수를 구했다.

 

주의할점은 n자리의 형태를 유지해야한다는 것이다. 만약 4자리수일 경우 1이 아니라 0001 이다.

최대층이 1234층이라고 하고, 현재층이 0012 층일 경우,

0012 에서 0001 로 바꾸는데 필요한 횟수,

0012 에서 0002 로 바꾸는데 필요한 횟수 .... 1234로 바꾸는데 필요한 횟수를 구하는 것이다.

 

앞서 map에 값을 저장했기 떄문에 각 자리를 변경시키는데 반전횟수를 구해서 가능여부를 판단하면 된다.

 

 

 

코드

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

public class Main {

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int answer = 0;

        int nn = Integer.parseInt(st.nextToken()); // 최대수
        int kn = Integer.parseInt(st.nextToken()); // 엘레베이터 자리수
        int pn = Integer.parseInt(st.nextToken()); // 반전 가능 개수
        int xn = Integer.parseInt(st.nextToken()); // 현재 엘레베이터 위치

        Map<Integer, HashMap<Integer, Integer>> map = new HashMap<>();

        int[][] numbers = new int[10][7];
        numbers[0] = new int[]{0, 0, 0, 1, 0, 0, 0};
        numbers[1] = new int[]{1, 1, 0, 1, 1, 0, 1};
        numbers[2] = new int[]{0, 1, 0, 0, 0, 1, 0};
        numbers[3] = new int[]{0, 1, 0, 0, 1, 0, 0};
        numbers[4] = new int[]{1, 0, 0, 0, 1, 0, 1};
        numbers[5] = new int[]{0, 0, 1, 0, 1, 0, 0};
        numbers[6] = new int[]{0, 0, 1, 0, 0, 0, 0};
        numbers[7] = new int[]{0, 1, 0, 1, 1, 0, 1};
        numbers[8] = new int[]{0, 0, 0, 0, 0, 0, 0};
        numbers[9] = new int[]{0, 0, 0, 0, 1, 0, 0};

        for (int i = 0; i < 10; i++) {
            map.put(i, new HashMap<>());
        }

        // 각 숫자에서 다른 숫자로 갈 때 필요한 반전의 개수를 구하자.
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                int count = 0;
                for (int k = 0; k < 7; k++) {
                    if(numbers[i][k] != numbers[j][k]){
                        count++;
                    }
                }
                // i 에서 j로 갈 때 count 만큼의 반전이 필요하다.
                map.get(i).put(j, count);
            }
        }

        String base = Integer.toString(xn);
        int baseLen = base.length();
        for (int i = 0; i < kn - baseLen; i++) {
            base = "0" + base;
        }

        // 해당 숫자가 1부터 nn 까지 변경이 가능한지 확인한다.
        for (int i = 1; i <= nn; i++) {
            String target = Integer.toString(i);
            int targetLen = target.length();
            for(int j=0; j< kn - targetLen; j++){
                target = "0" + target; // 빈자리는 0으로 채운다.
            }

            // 각 자리에서 target 자리로 변경하는데 필요한 반전 개수의 합을 구한다.
            int count = 0;
            for (int j = 0; j < kn; j++) {
                count += map.get(base.charAt(j) - '0').get(target.charAt(j) - '0');
            }


            if(count <= pn) answer++;
        }

        System.out.println(answer-1);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

후기