2147. Number of Ways to Divide a Long Corridor

[zeikar]

Problem link

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

Problem Summary

의자와 식물이 있을 때 의자를 2개씩 묶을 수 있는 경우의 수를 구하는 문제.

Solution

딱 보니 DP 냄새가 나서 탑 다운으로 풀었는데 ... 메모리 초과가 난다.
바텀업으로 고치니 통과!
또, 2차원 DP를 1차원으로 줄이니 더 빨라지고 메모리도 적게 먹는다.

간단하게 설명하자면

DP[i][j] = i번째 인덱스까지 의자가 j개 나왔을 때의 경우의 수

로 정의하고 점화식을 만들 수 있다. 그리고 for문을 돌면서 덮어 씌워지므로 1차원으로 줄일 수 있다.

추가로 수학적인 풀이도 존재하는데, 의자는 무조건 2개씩 붙여야 하므로 경우의 수는 식물이 메인이 되고 의자가 2개씩 나온 사이의 식물들이 모여져 있는 카운트를 센 다음 다 곱하면 최종 경우의 수가 된다. 아래 디스커션 참고.

https://leetcode.com/problems/number-of-ways-to-divide-a-long-corridor/discuss/1709704/Greedy-Solution-or-C%2B%2B

Source Code

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        n = len(corridor)

        dp = [0] * 3
        dp[0] = 1

        for i in range(n):
            if corridor[i] == 'S':
                dp[0], dp[1], dp[2] = 0, dp[0] + dp[2], dp[1]
            else:
                dp[0], dp[1], dp[2] = dp[0] + dp[2], dp[1], dp[2]

        return dp[2] % (10 ** 9 + 7)