99클럽 코테 스터디 42일차 TIL + DP

[오늘의 학습 키워드 및 문제]
- 리트코드의 "First Day Where You Have Been in All the Rooms" 문제를 풀었다.
- 마지막날 주제는 바로 DP(다이나믹 프로그래밍)이다.

[나의 코드]

class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
        MOD = 10 ** 9 + 7
        n = len(nextVisit)
        dp = [0] * n
        
        for i in range(n - 1):
            dp[i + 1] += (2 * dp[i] - dp[nextVisit[i]] + 2) % MOD
    
        return dp[-1]

이 문제를 그래프라고 생각을 해보자.
하나는 짝수 번을 방문한 경우, 다른 하나는 홀수 번 방문한 경우로 나눠서 생각해 볼 수 있다.

중요한 점은 특정 노드에서 다음 노드로 이동하기까지 그 노드의 방문 횟수가 짝수가 되어야 한다. 또한 이전의 모든 노드들은 다음 노드를 방문할 수 있도록 짝수 번을 들렀다는 것을 알 수 있다.

[오늘의 회고]
- 드디어 마지막 날이다. 여기까지 온 걸 자랑스럽게 여기자. 호호
- 수고했습니다. 끝!