[LeetCode] 2147. Number of Ways to Divide a Long Corridor

https://leetcode.com/problems/number-of-ways-to-divide-a-long-corridor/description/

Number of Ways to Divide a Long Corridor - LeetCode

leetcode - Number of Ways to Divide a Long Corridor

문제 유형 : 수학, 다이나믹 프로그래밍, 조합

문제 난이도 : Hard

 

문제

Along a long library corridor, there is a line of seats and decorative plants. You are given a 0-indexed string corridor of length n consisting of letters 'S' and 'P' where each 'S' represents a seat and each 'P' represents a plant.

One room divider has already been installed to the left of index 0, and another to the right of index n - 1. Additional room dividers can be installed. For each position between indices i - 1 and i (1 <= i <= n - 1), at most one divider can be installed.

Divide the corridor into non-overlapping sections, where each section has exactly two seats with any number of plants. There may be multiple ways to perform the division. Two ways are different if there is a position with a room divider installed in the first way but not in the second way.

Return the number of ways to divide the corridor. Since the answer may be very large, return it modulo 10⁹ + 7. If there is no way, return 0.

 

긴 도서관의 복도가 있다. 일렬로 좌석과 데코용 식물이 있다.

당신은 n의 길이의 문자열 corridor를 받고, 'S'는 좌석, 'P'는 식물을 의미한다.

 

하나의 파티션은 인덱스 0의 왼쪽에, 또 하나는 인덱스 n-1의 오른쪽에 있다.

당신은 파티션을 추가하여 각 섹션별로 좌석이 두 개씩 있도록 나누어야 한다. 

다양한 방법이 있을 수 있다.

이 복도를 분할하는 모든 경우의 수를 구하여라. 답이 커질 수 있으니, 1e9 + 7로 나눈 나머지를 반환하라.

방법이 없다면, 0을 반환하라.

 

 

풀이

두 쌍의 좌석들 간의 파티션을 두는 경우의 수는 오른쪽 쌍의 첫 번째 좌석의 인덱스 - 왼쪽 쌍의 두 번째 좌석의 인덱스이다.

인접한 두 쌍들끼리의 각각의 경우의수들을 구해서 모두 곱해주면 된다.

 

 

코드

C++

class Solution {
public:
    int numberOfWays(string corridor) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        const int MOD = 1e9+7;
        const int n = corridor.size();
        if(n == 1) return 0;
        vector<pair<int, int>> seats;
        int s1 = -1, s2 = -1; // seat temporary Idx

        for(int i = 0; i < n; i++) {
            if(corridor[i] == 'S') {
                if(s1 == -1) {
                    s1 = i;
                } else if(s2 == -1) {
                    s2 = i;
                    seats.push_back({s1, s2});
                    s1 = -1;
                    s2 = -1;
                }
            }
        }

        // no way(pair doesn't match)
        if(s1 != -1 && s2 == -1) {
            return 0;
        }

        // if corridor has no pair
        if(seats.size() == 0) return 0;
        // if there is only one pair, we don't need to divide.
        if(seats.size() == 1) return 1;
        // multiply cases
        long long answer = 1;
        for(int i = 0; i < seats.size()-1; i++) {
            int num = seats[i+1].first - seats[i].second;
            answer = (answer * num) % MOD;
        }

        return answer % MOD;
    }
};