2222. Number of Ways to Select Buildings

2222. Number of Ways to Select Buildings

https://leetcode.com/problems/number-of-ways-to-select-buildings/

문제

풀이(DP)

문제에서 3개의 빌딩이라는 조건이 주었다.
그래서 나올 수 있는 것이 첫 번째 자리가 0일 때 010, 또는 첫 번째 자리가 1일 때 101 이렇게 2가지만 나올 수 있다.
따라서 첫째 자리 숫자를 기준으로 01, 10이 몇개 있는지만 알면 되는 문제였다.
각 인덱스마다 01, 10이 몇개 있는지 알기 위해서 다음과 같이 풀었다.

zero에는 인덱스마다 0이 몇개 있는지, one에는 인덱스마다 1이 몇개 있는지 저장한다.

zeroone, onezero 점화식은 밑에와 같은데

		if s[i] == "0":
            zeroone[i] = one[i] + zeroone[i+1]
            onezero[i] = onezero[i+1]
        else:
            zeroone[i] = zeroone[i+1]
            onezero[i] = zero[i] + onezero[i+1]

인덱스 별로 01, 10을 알 수 있다.

결과(DP)