99클럽 코테 스터디 42일차 TIL , First Day Where You Have Been in All the Rooms

문제

풀이

너무너무 어렵다..

처음에 무조건 0에 방문하는데 그게 첫 번째 방문이다.

만약 방문이 홀수일 때 다음 날 nextVisit[i]를 방문한다.

짝수 일 때 다음 날 i+1을 방문한다.

여기까지가 내가 생각한 부분이고 규칙을 찾으려고 하다가 실패해서 결국 다른 사람들의 풀이를 봤다..

근데 이해가 잘 안된다...

 

다른 사람의 풀이 참고

class Solution {
    public int firstDayBeenInAllRooms(int[] nextVisit) {
        long mod = 1_000_000_007l;
        int[] dp = new int[nextVisit.length];
        
        for(int i=1;i<nextVisit.length;i++){
            long tmp = dp[i-1] + 2 + dp[i-1] - dp[nextVisit[i-1]] + mod;
            
            dp[i] = (int)(tmp  % mod);
        }
        
        return dp[nextVisit.length-1];
    }
}

 

다음으로 가는 경우에는 i-1에서 바로 넘어오거나 홀 수라서 다른 방문을 반복한 후 다음으로 넘어간다.

여기까지는 오케이 하겠는데 식이 왜 저렇게 만들어지는지는 진짜 모르겠다..

그냥 반복해서 보는 수밖에 없을 것 같다..

TIL

• 오늘 약간의 좌절감을 느꼈다. 나는 이 문제를 이해하는데 까지도 오래 걸렸고 다른 사람의 풀이를 봐도 너무 어렵다.