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

https://leetcode.com/problems/number-of-ways-to-divide-a-long-corridor/description/?envType=daily-question&envId=2023-11-28

Number of Ways to Divide a Long Corridor - LeetCode

2147. Number of Ways to Divide a long Corridor - Hard

 

 

 

복도에 소파와 화분이 있다. 이 복도를 구역으로 나누는데 각 구역에는 무조건 소파가 두개씩 있어야한다.

구역을 나누는 방법은 몇가지인지 찾는 문제.

 

Hard 치고는 꽤 쉬운 편.

구역마다 첫 소파와 두번째 소파가 있을것이다.

뒷 구역의 첫 소파의 index에서 앞 구역의 첫 소파의 index를 빼주고,

경우의 수들을 계속 곱해주면 된다.

 

class Solution {
public:
    int numberOfWays(string corridor) {
        long long r = 1;
        int f = 0, s = 0;
        for (int i = 0, b = -1; i < corridor.size(); i++) {
            if (corridor[i]=='S') {
                s = 1;
                if (!f && b>-1) r = (r * (i - b)) % 1000000007;
                else if (f) b = i;
                f = 1-f;
            }
        }
        return !f && s ? r:0;
    }
};