백준 1089 스타트링크 타워 python, java

시간초과를 전구 on off 에 따른 가짓수에서 최적화를 시켜보려고 했는데 정작 문제는 평균을 구하는 곳에서 발생했었다.
최대 가능한 경우의 수가 0 ~ 999999999 까지 였기때문에 이숫자를 하나하나 더해주는 것만으로 시간초과가 발생한다. 덧셈부분에 대해 다른 방법이 필요했다.

📜 문제 바로 가기 : 스타트링크 타워

제출코드

파이썬

import sys
input = sys.stdin.readline

numberPicture = [
    ["###", "#.#", "#.#", "#.#", "###"], # 0
    ["..#", "..#", "..#", "..#", "..#"], # 1
    ["###", "..#", "###", "#..", "###"], # 2
    ["###", "..#", "###", "..#", "###"], # 3
    ["#.#", "#.#", "###", "..#", "..#"], # 4
    ["###", "#..", "###", "..#", "###"], # 5
    ["###", "#..", "###", "#.#", "###"], # 6
    ["###", "..#", "..#", "..#", "..#"], # 7
    ["###", "#.#", "###", "#.#", "###"], # 8
    ["###", "#.#", "###", "..#", "###"]  # 9
]


N = int(input())
numberBoard = [input().rstrip() for _ in range(5)]
floor = [[False]*10 for _ in range(N)] # N층에 올 수 있는 번호 경우의 수

for k in range(N):
    arr = []
    for i in range(5):
        arr.append(numberBoard[i][k*4 : k*4+3])
    
    for num in range(10):
        isPossible = True
        for i in range(5):
            for j in range(3):
                if numberPicture[num][i][j] != arr[i][j] and arr[i][j] == "#":
                    isPossible = False
                    break
            if isPossible == False:
                break
    
        if isPossible == True:
            floor[k][num] = True

flag = True
for i in range(N):
    for j in floor[i]:
        if j == True:
            break
    else:
        flag = False
        break

def calculate():
    cnt = 1 # 전체 경우수
    cnt_arr = [0] * N
    for i in range(N):
        c = 0
        for j in floor[i]:
            if j == True:
                c += 1
        cnt_arr[i] = c 
        cnt *= c
    
    value = 0
    for i in range(N):
        # N-i 자릿수
        i_cnt = cnt // cnt_arr[i] # N=i 자릿수의 값이 등장하는 횟수
        for j in range(10):
            if floor[i][j] == True:
                value += j * 10**(N-i-1) * i_cnt

    return value / cnt

if flag == True:
    ans = calculate()
else:
    ans = -1

print(ans)

자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static String[][] numberPicture = {
            {"###", "#.#", "#.#", "#.#", "###"}, // 0
            {"..#", "..#", "..#", "..#", "..#"}, // 1
            {"###", "..#", "###", "#..", "###"}, // 2
            {"###", "..#", "###", "..#", "###"}, // 3
            {"#.#", "#.#", "###", "..#", "..#"}, // 4
            {"###", "#..", "###", "..#", "###"}, // 5
            {"###", "#..", "###", "#.#", "###"}, // 6
            {"###", "..#", "..#", "..#", "..#"}, // 7
            {"###", "#.#", "###", "#.#", "###"}, // 8
            {"###", "#.#", "###", "..#", "###"}  // 9
    };

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

        int N = Integer.parseInt(br.readLine());
        char[][] numberBoard = new char[5][3*N + N-1];
        boolean[][] floor = new boolean[N][10];

        for (int i = 0; i < 5; i++) {
            int j = 0;
            for (char c : br.readLine().toCharArray()) {
                numberBoard[i][j] = c;
                j += 1;
            }
        }

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

            for (int num = 0; num < 10; num ++) {
                Boolean isPossible = true;
                for (int i = 0; i < 5; i++) {
                    String nP =  numberPicture[num][i];
                    for (int j = 0; j < 3; j++) {
                        char c = nP.charAt(j);
                        if ((c != numberBoard[i][k*4+j]) && ('#' == numberBoard[i][k * 4 + j])) {
                            isPossible = false;
                            break;
                        }
                    }

                    if (isPossible == false) {
                        break;
                    }
                }

                if (isPossible == true) {
                    floor[k][num] = true;
                }
            }
        }

        Boolean flag = true;
        for (int i = 0; i < N; i++) {
            Boolean for_else = true;
            for (Boolean j : floor[i]) {
                if (j == true) {
                    for_else = false;
                    break;
                }
            }
            if (for_else == true) {
                flag = false;
                break;
            }
        }

        double ans = -1;
        if (flag == true) {
            double cnt = 1;
            int[] cnt_arr = new int[N];
            for (int i = 0; i < N; i++) {
                cnt_arr[i] = 0;
            }

            for (int i = 0; i < N; i++) {
                int c = 0;
                for (Boolean j : floor[i]) {
                    if (j==true) {
                        c += 1;
                    }
                }
                cnt_arr[i] = c;
                cnt *= c;
            }

            double value = 0;
            for (int i = 0; i < N; i++) {
                double i_cnt = cnt /  cnt_arr[i];
                for (int j = 0; j < 10; j++) {
                    if (floor[i][j] == true) {
                        value += j * Math.pow(10, N-i-1) * i_cnt;
                    }
                }
            }

            ans = value / cnt;
        }

        System.out.println(ans);
    }
}

---

접근방법

ABC 3자리 칸이 있고 A = [1, 2, 3], B = [4, 5], C = [6, 7, 8, 9] 숫자가 올 수 있다고 하자.
그럼 먼저 조합가능한 숫자의 경우의 수는 3 x 2 x 4 = 24가지가 나온다.
그리고 우리의 목표는 24가지 숫자를 하나하나 다 만들어서 더하는 것이 아니다.

A자리에 1이 올때 가능한 숫자는 146, 147, ..., 159 까지 8개이다.
A자리에 2가 온다면? 역시 8개이다.

그렇다면 이번엔 B를 고정시켜보자.
B가 4일때 조합가능한 경우는? 12개가 나온다. 5일때도 역시 12개이다.
규칙이 보인다.
전체 경우의수에서 해당 자리의 숫자 개수를 나눠주면 된다.

이를 이용하면 C가 6일때 가능한 숫자개수는 24 / 4 = 6개임을 한번의 연산으로 알 수 있다.

평균을 구하기 위해 전체 경우 수의 덧셈. 즉, 총합이 필요한데 이를 이용하여 빠르게 구할 수 있다.
위에서 A가 1일때 나오는 숫자는 8개임을 알았다. B, C 가 뭔지는 모르겠는데, 1xx, 1xx, 1xx, 이런 숫자가 8개 있다는 소리다. 즉, 100 이 8번 있다는것을 보장해준다.

각 자리수의 숫자가 몇번 등장하는지 알 수 있다면 결국 총합의 연산을 훨씬 적은 연산으로 구할 수 있게 된다.