본문으로 건너뛰기

22251 - 빌런 호석

정보
  • 문제 보기: 22251 - 빌런 호석
  • 소요 시간: 52분 15초
  • 풀이 언어: java
  • 체감 난이도: 3️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

구현 완전탐색


풀이 코드​

정보
  • 메모리: 52224 KB
  • 시간: 168 ms
import java.util.*;
import java.io.*;

public class Main
{
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int n, k, p, x;
    static int[][] cost = {
        // 7-세그먼트 거리 행렬
        // 계산하는데 10분 걸림 ^ㅍ^
        {0, 4, 3, 3, 4, 3, 2, 3, 1, 2}, // 0 -> x
        {4, 0, 5, 3, 2, 5, 6, 1, 5, 4}, // 1 -> x
        {3, 5, 0, 2, 5, 4, 3, 4, 2, 3}, // 2 -> x
        {3, 3, 2, 0, 3, 2, 3, 2, 2, 1}, // 3 -> x
        {4, 2, 5, 3, 0, 3, 4, 3, 3, 2}, // 4 -> x
        {3, 5, 4, 2, 3, 0, 1, 4, 2, 1}, // 5 -> x
        {2, 6, 3, 3, 4, 1, 0, 5, 1, 2}, // 6 -> x
        {3, 1, 4, 2, 3, 4, 5, 0, 4, 3}, // 7 -> x
        {1, 5, 2, 2, 3, 2, 1, 4, 0, 1}, // 8 -> x
        {2, 4, 3, 1, 2, 1, 2, 3, 1, 0}, // 9 -> x
    };
    
    public static void main(String[] args) throws IOException {
        n = nextInt();
        k = nextInt();
        p = nextInt();
        x = nextInt();
        
        // 반전 후 1 ~ n 이 되도록 할 것임
        // 디스플레이는 k 자릿수임
        // 최대 p개의 led를 반전할 것
        // 실제로는 x층임
        
        // 최악 100만에 대해 BF로 p 이내에 반전이 가능한지 여부 검사
        // 가능하면 반전 비용 합산
        
        int ans = 0;
        
        // 원본 x값에 대한 k 자릿수 고정의 digit 배열
        int[] fromDigitArr = new int[k];
        int idx = fromDigitArr.length - 1;
        int xCpy = x;
        while (xCpy > 0) {
            fromDigitArr[idx--] = xCpy % 10;
            xCpy /= 10;
        }
        
tfor:   for (int target = 1; target <= n; ++target) {
            if (x == target) continue;
            
            // 바꿔놓을 target값에 대한 k 자릿수 고정의 digit 배열
            int[] toDigitArr = new int[k];
            idx = toDigitArr.length - 1;
            int targetCpy = target;
            while (targetCpy > 0) {
                toDigitArr[idx--] = targetCpy % 10;
                targetCpy /= 10;
            }
            
            int costSum = 0;
            for (int i = 0; i < fromDigitArr.length; ++i) {
                int a = fromDigitArr[i];
                int b = toDigitArr[i];
                
                if (a == b) continue; // 숫자 같으면 안바꿈
                
                costSum += cost[a][b];
                if (costSum > p) continue tfor; // 반전 가능 최대치를 초과함
            }
            
            ans += 1; // 경우의 수 카운트
        }
        
        System.out.println(ans);
    }
    
    static int nextInt() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
}

풀이 해설​

처음에 약간 난독이 왔는데, 범위를 따져보면 호석이가 바꿔놓을 결과의 경우의 수가 최악 100만 가지이고,

최대 LED는 k 자리이기 때문에, naive한 시간복잡도는 O(1,000,000×6)O(1{,}000{,}000 \times 6) 이라고 볼 수 있다.

그래서 완탐으로 가능 여부 각 재보며 경우의 수 카운팅하면 되는 문제이다.


✍️ 풀이 과정 요약​

  1. 세그먼트 거리 행렬 하드코딩하기
  2. 원본값 x를 배열화하기
  3. 목표값 target을 배열화하기
  4. 자릿수대로 cost 비교
    • 같은 숫자이면 굳이 안바꾼다.
    • cost 합이 p를 초과하면 중단하고 바로 다음 target으로 continue 한다.

반드시 copy 하기

x와 target은 반드시 복사한 값을 while 문에서 처리해야 한다.
복사하지 않으면 라인 48 ~ 49 단에서 for 반복문 카운터에 영향이 가고
그 아래의 continue 조건에도 영향이 가면서, 1차적으로 무한루프 문제가 발생하게 된다.


메모​

  • 자바에서 new로 생성한건 local scope여도 자동 0 초기화 되어있음
  • 생각보다 세그먼트 행렬 노가다 하는데 10분밖에(^^) 걸리지 않았음
    • 실전에서도 괜춘할듯?
  • 나쁘지 않은 구현 문제인데 실전보다는 쉽다고 느낌.