[JAVA] BOJ1089 스타트링크 타워

알고리즘 분류

• 수학
• 구현
• 확률론

문제 풀이 방법

nums 배열에서 구역을 알면 어떤 수인지 알 수 있습니다.

• nums[행][0] ~ nums[행][2] 일 때는 1
• nums[행][4] ~ nums[행][6] 일 때는 2
• nums[행][8] ~ nums[행][10] 일 때는 3
• ...
• nums[행][32] ~ nums[행][34] 일 때는 9

ArrayList 배열은 각 idx번째에서 어떤 정수를 가질 수 있는지 저장합니다.

• e.g) list[0]: 0번째 위치에서 가질 수 있는 숫자들 (조건을 판단해서 가능한 것들을 ArrayList구조로 저장함)

map과 nums를 비교하면서 현재 map의 범위에서 가능한 경우를 list에 저장합니다.

• checkNums 함수에서 구현하였습니다.
  • 각 자릿수에서 가능한 정수들을 다 구했다면, 각 경우의 수의 합을 구해줍니다.
  • 저는 자릿수마다 경우를 나누어서 생각했습니다.
• 만약 총 세 자리 수이고, 첫 번째, 두 번째, 세번째 수에서 모두 0~9 가 가능하다면,,,
  • 첫 번째 자리 수에서 가능한 경우에서 모든 합 (100의 자리)
    • (1부터 9까지의 합) * (자리수에 대한 값) * (나머지 자리수가 배치될 수 있는 경우의 수)
    • (45) * (100) * (10가지 * 10가지) = 450,000
  • 두 번째 자리 수에서 가능한 경우에서 모든 합 (10의 자리)
    • (1부터 9까지의 합) * (자리수에 대한 값) * (나머지 자리수가 배치될 수 있는 경우의 수)
    • (45) * (10) * (10가지 * 10가지) = 45,000
  • 세 번째 자리 수에서 가능한 경우에서 모든 합 (1의 자리)
    • (1부터 9까지의 합) * (자리수에 대한 값) * (나머지 자리수가 배치될 수 있는 경우의 수)
    • (45) * (1) * (10가지 * 10가지) = 4,500
  • 따라서 이 경우, 모든 안내판이 나타내고 있는 모든 층 번호의 합은 450,000 + 45,000 + 4,500 = 499,500 이고, 가능한 모든 경우의 수는 (10가지) * (10가지) * (10가지) 이므로 정답은 499.5가 됩니다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    static String nums[] = {"###...#.###.###.#.#.###.###.###.###.###",
                            "#.#...#...#...#.#.#.#...#.....#.#.#.#.#",
                            "#.#...#.###.###.###.###.###...#.###.###",
                            "#.#...#.#.....#...#...#.#.#...#.#.#...#",
                            "###...#.###.###...#.###.###...#.###.###"};
    static char map[][];
    static ArrayList<Integer> availNums[];

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

        int N = Integer.parseInt(br.readLine());
        map = new char[5][N * 3 + (N - 1)];
        availNums = new ArrayList[N];
        for(int i = 0; i < availNums.length; i++) availNums[i] = new ArrayList<>();

        for(int r = 0; r < 5; r++) {
            String input = br.readLine();
            map[r] = input.toCharArray();
        }

        ArrayList<Point> points = new ArrayList<>();

        for(int k = 0; k < N; k++) {
            points.clear();

            for(int r = 0; r < 5; r++) {

                for(int c = 0; c < 3; c++) {
                    if(map[r][k * 4 + c] == '#') points.add(new Point(r, c));
                }
            }

            if(points.isEmpty()) {
                for(int i = 0; i < 10; i++) availNums[k].add(i);
            } else {
                checkNums(k, points);
            }
        }

        double result = 0;
        int totalCnt = 0;
        int totalResultCount = 1;

        for(int i = 0; i < availNums.length; i++) {
            if(availNums[i].size() == 0) continue;
            totalCnt += availNums[i].size();
            totalResultCount *= availNums[i].size();
        }

        int k = 0;
        for(int i = availNums.length - 1; i >= 0; i--) {
            long tmp = (int) Math.pow(10, k);
            long sum = 0;

            for(int num: availNums[i]) sum += tmp * num;
            if(N == 1) result += sum;
            else result += sum * (returnRemain(i));
            k++;
        }

        result = result * 1.0 / totalResultCount == 0 ? -1: result * 1.0 / totalResultCount;
        System.out.println(result);
    }

    private static long returnRemain(int idx) {

        int k = 1;
        for(int i = 0; i < availNums.length; i++) {
            if(i == idx) continue;
            k *= availNums[i].size();
        }
        return k;
    }

    private static void checkNums(int idx, ArrayList<Point> points) {
        for(int num = 0; num < 10; num++) {
            boolean check = true;

            for(Point point: points) {
                if(!(nums[point.r].charAt(num * 4 + point.c) == '#')) {
                    check = false;
                    break;
                }
            }

            if(check) availNums[idx].add(num);
        }
    }
}

느낀점

문제풀이를 하다가 중간에 사고의 끈을 놔버려서 생각보다 시간이 오래 걸렸습니다. (문제 풀 때까지 끝난게 아니다 !!)
문제를 풀 때 생각, 사고하는게 뒤엉퀴지 않게 조금 더 의식적으로 집중해야될 것 같습니다.

 

다른 분은 좌표마다 어떤 위치에 '#' 이 있을 때, 만들 수 없는 숫자의 경우를 생각해서 풀이를 했다고 합니다 (굿아이디어)

한 가지 문제여도 풀이를 할 수 있는 방법은 많다는 것을 느꼈습니다. !!  (문제 해결 방법이 맞다면, 바로 구현하자 !)