[백준] 1089번. 스타트링크 타워(JAVA)

문제

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

---

풀이(30분)

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

public class Main {

    static final String[] NUMS = { // 0~9까지의 7-digit 숫자 저장
            "####.##.##.####",
            "..#..#..#..#..#",
            "###..#####..###",
            "###..####..####",
            "#.##.####..#..#",
            "####..###..####",
            "####..####.####",
            "###..#..#..#..#",
            "####.#####.####",
            "####.####..####"
    };

    static int n;
    static char[][] map;
    static List<Point> pointList = new ArrayList<>();

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

        n = Integer.parseInt(br.readLine());
        map = new char[5][4 * n - 1]; // 입력 문자 저장

        for (int i = 0; i < 5; i++) {
            String line = br.readLine();
            for (int j = 0; j < line.length(); j++) {
                map[i][j] = line.charAt(j);
            }
        }

        for (int digitIdx = 0; digitIdx < n; digitIdx++) {
            List<Integer> possibleNumbers = new ArrayList<>();
            for (int num = 0; num < 10; num++) {
                if (isValidNumber(digitIdx, num)) {
                    possibleNumbers.add(num);
                }
            }
            if (possibleNumbers.isEmpty()) {
                System.out.println("-1");
                return;
            }
            pointList.add(new Point(0, digitIdx, possibleNumbers));
        }

        double sum = calculateExpectedValue();
        System.out.println(sum);
    }

    public static class Point {
        int row, col;
        List<Integer> possibleNumbers;

        public Point(int row, int col, List<Integer> possibleNumbers) {
            this.row = row;
            this.col = col;
            this.possibleNumbers = possibleNumbers;
        }
    }

    static boolean isValidNumber(int digitIdx, int compareTo) {
        int startIdx = digitIdx * 4;  // 숫자 시작 위치
        for (int row = 0; row < 5; row++) {
            for (int col = 0; col < 3; col++) {
                char expected = NUMS[compareTo].charAt(row * 3 + col);
                char actual = map[row][startIdx + col];
                if (actual != '.' && actual != expected) {
                    return false;
                }
            }
        }
        return true;
    }

    static double calculateExpectedValue() {
        int totalCases = 1;
        int[] digitCases = new int[n];
        Arrays.fill(digitCases, 1);

        for (int i = 0; i < n; i++) {
            totalCases *= pointList.get(i).possibleNumbers.size();
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    digitCases[j] *= pointList.get(i).possibleNumbers.size();
                }
            }
        }

        double sum = 0;
        for (int i = 0; i < n; i++) {
            double weight = (double) digitCases[i] / totalCases;
            for (int num : pointList.get(i).possibleNumbers) {
                sum += num * Math.pow(10, n - 1 - i) * weight;
            }
        }
        return sum;
    }
}

---

문제 풀이 전략

 

아이디어보다는 구현이 매우 복잡한 문제였다.

 

천천히 살펴보자. 대표적인 아이디어는 다음과 같다.

 

문자열을 살펴보며 한 칸마다 만들 수 있는 문자를 추가해 준다.

이후 모든 자리에 대해 비교하며 자리마다 만들 수 있는 문자를 구한다.

 

최종적으로 나머지 자리로 만들 수 있는 경우의 수에 현재 자리에서 가능한 수를 곱해준다.

 

다음과 같이 아이디어는 심플하다. 이를 구현하는 과정이 중요하다고 생각한다.

시간이 나면 꼭 다시 한번 더욱 좋은 구현을 연습해봐야 할 것 같다.