[BOJ 1089] 스타트링크 타워(C++)

스타트링크 타워(Gold 5)

문제

전체 문제 보기

1089번: 스타트링크 타워

접근법

이번 문제에서 이차원 배열을 탐색하여 표현 가능한 숫자를 만드는 부분을 구현하는 것과, 가능한 숫자들을 조합하여 만들어진 수의 평균값을 "빠르게" 계산하는 것이 핵심입니다. 이차원 배열을 탐색하여 표현 가능한 숫자를 만드는 부분은 생각보다 간단하게 구현할 수 있지만, 조합하여 만들어진 수의 평균값을 "빠르게" 계산하는 것은 비교적 쉽게 떠올리기 어려웠습니다. 조합하여 만들어질 수 있는 수의 최대 크기는 \(10^n\) 이기 때문에 직접 모두 계산할 경우 다음과 같이 시간 초과 혹은 메모리 초과가 발생할 수 있습니다.

우리는 만들어질 수 있는 수의 평균값만 계산하는 것이지, 그 수들을 모두 구할 필요는 없습니다. 때문에 직접 수들을 구성하기 보다는 평균만 빠르게 계산하는 방법으로 접근하여 풀이할 수 있습니다. 이에 대한 설명이 이 곳을 참고하였습니다.

전체 소스 코드

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <set>
#include <cmath>
const std::array<std::string, 5> numbers
{
    "###...#.###.###.#.#.###.###.###.###.###",
    "#.#...#...#...#.#.#.#...#.....#.#.#.#.#",
    "#.#...#.###.###.###.###.###...#.###.###",
    "#.#...#.#.....#...#...#.#.#...#.#.#...#",
    "###...#.###.###...#.###.###...#.###.###"
};

void AddCandidate(int pos, std::vector<int>& candidate, std::array<std::string, 5>& number_plate, int N)
{
    for (int n = 0; n < 10; n++)
    {
        bool is_candidate = true;
        for (int r = 0; r < 5; ++r)
        {
            for (int c = 0; c <  3; c++)
            {
                if (numbers[r][c + (n * 4)] == '.' && number_plate[r][c + (pos * 4)] == '#')
                {
                    is_candidate = false;
                    goto is_not_candidate; // 다중 반복문시 break 대신 사용할 수 있습니다. 
                }
            }
        }
    is_not_candidate:

        if (is_candidate)
            candidate.push_back(n * (int)std::pow(10, N - pos - 1));
    }
}

int main()
{
    //입출력 성능향상을 위한 설정
    std::ios_base::sync_with_stdio(false);
    std::cout.tie(NULL);
    std::cin.tie(NULL);

    std::array<std::string, 5> number_plate;
    std::vector<std::vector<int>> candidate_numbers;
    int N; // N은 9보다 작거나 같은 자연수

    std::cin >> N;
    candidate_numbers.resize(N);
    for (int i = 0; i < 5; i++)
        std::cin >> number_plate[i];

    long long cnt = 1;
    for (int i = 0; i < N; ++i)
    {
        AddCandidate(i, candidate_numbers[i], number_plate, N);
        cnt *= candidate_numbers[i].size();
    }
    if (cnt == 0)
    {
        // 가능한 층 번호가 없음.
        std::cout << -1 << '\n';
        return 0;
    }

    long long sum{};
    for (int i = 0; i < N; ++i)
    {
        long long temp{};
        for (int c : candidate_numbers[i])
        {
            temp += c;
        }
        sum += temp * (cnt / candidate_numbers[i].size());
    }

    double answer = sum / (double)cnt;

    std::cout << answer << '\n';
    return 0;
}