[LeetCode] 2327. Number of People Aware of a Secret

문제

 

비밀을 알고 있는 사람의 수를 구하는 문제이다. 총 일 수인 n, 비밀을 알게 된 사람은 delay 일이 지나고 나서부터 다른 사람에게 비밀을 말할 수 있고, forget일이 지난 후 이 비밀을 까먹게 된다. 마지막 n일이 끝나고 나서 아는 사람의 수를 구하는 문제인데, 수가 너무 커질 수도 있어 결과는 modulo인 10⁹ + 7로 나눈 나머지로 반환한다. 

 

풀이

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        Mod = 10 ** 9 + 7
        #비밀을 알고 있는 사람들의 수를 저장, secret[n]은 n번째 날에 비밀을 알고 있는 사람 수
        secret = [0] * (n + 1)
        secret[1] = 1   #첫째 날에는 한 사람만 아므로 1로 설정

        for days in range(2, n+1) :
            #delay ~ forget일까지 
            for forget_time in range(delay, forget) : 
                if days - forget_time >= 1 :
                    secret[days] = (secret[days] + secret[days - forget_time]) % Mod

        
        #n + 1 - forget 일 부터 n까지의 날짜 : 비밀을 잊지 않은 사람
        return sum(secret[n + 1 - forget:]) % Mod

 

1. 먼저 비밀을 알고 있는 사람의 수를 저장할 secret 배열을 선언한다. 처음엔 0으로 초기화되어 있고, 길이는 n+1이 된다.
2. secret[n]에는 n번째 날에 비밀을 알고 있는 사람 수가 저장되는데, 첫째 날에는 한 명이 알고 있기 때문에 secret[1]을 1로 초기화한다.
3. 이후 2일부터 n일까지 반복하게 되는데, 새롭게 알게되는 사람들과 까먹는 사람을 한 번에 기록하기 위해 delay일부터 forget일까지 계산한다.
4. days - forget_time >= 1인경우(새롭게 알게 되는 사람이 있는 경우) secret[days - forget_time]에 있는 사람들 수 만큼 새로운 사람에게 알리게 되므로 아는 사람의 수를 추가적으로 갱신한다. 이 때 결과를 유지하기 위해 Mod로 나눈 나머지 이용
5.  n + 1 - forget일 부터 n일까지 비밀을 아는 사람들의 수를  sum한 값을 mod로 나누어 나머지를 반환한다.