3179. Find the N-th Value After K Seconds / TypeScript

You are given two integers n and k.

Initially, you start with an array a of n integers where a[i] = 1 for all 0 <= i <= n - 1. After each second, you simultaneously update each element to be the sum of all its preceding elements plus the element itself. For example, after one second, a[0] remains the same, a[1] becomes a[0] + a[1], a[2] becomes a[0] + a[1] + a[2], and so on.

Return the value of a[n - 1] after k seconds.

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: n = 4, k = 5

Output: 56

Explanation:

SecondState After

0	[1,1,1,1]
1	[1,2,3,4]
2	[1,3,6,10]
3	[1,4,10,20]
4	[1,5,15,35]
5	[1,6,21,56]

Example 2:

Input: n = 5, k = 3

Output: 35

Explanation:

SecondState After

0	[1,1,1,1,1]
1	[1,2,3,4,5]
2	[1,3,6,10,15]
3	[1,4,10,20,35]

출처 : https://leetcode.com/problems/find-the-n-th-value-after-k-seconds/description/

 

 

풀이 

function valueAfterKSeconds(n: number, k: number): number {  
    let nums: number[] = new Array(n).fill(1);
    
    let mod = 1e9+7;
    
    while (k > 0) {
        let sum: number = 0;
        for (let i = 0; i < n; i++) {
            sum += nums[i];
            sum %= mod;
            nums[i] = sum;
        }
        k--;
    }
    
    return nums[n - 1];
};

 

 

sum += nums[i];

이 줄은 nums[i]의 현재 값을 sum에 더함. sum은 현재까지의 누적 합을 저장하는 변수

예를 들어, 첫 번째 루프의 초기 상태에서:

• sum은 0으로 초기화
• nums[i]는 배열의 현재 요소

만약 nums = [1, 1, 1, 1, 1]라면:

• i = 0일 때, sum = 0 + 1 = 1
• i = 1일 때, sum = 1 + 1 = 2
• i = 2일 때, sum = 2 + 1 = 3
• i = 3일 때, sum = 3 + 1 = 4
• i = 4일 때, sum = 4 + 1 = 5

sum %= mod;

이 줄은 sum의 값을 모듈러 연산(mod로 나눈 나머지)으로 업데이트

이는 sum이 너무 커지는 것을 방지하여, 큰 수를 다룰 때 발생할 수 있는 오버플로우를 피하는 역할을 함

예를 들어, mod가 1e9+7 (즉, 1000000007)이라고 가정

현재 sum이 이 값보다 크다면, sum은 mod로 나눈 나머지로 업데이트.

하지만 초기 값에서는 이 값이 작기 때문에 이 줄은 큰 영향을 미치지 않음

nums[i] = sum;

이 줄은 현재 배열의 요소 nums[i]를 sum 값으로 업데이트.

이렇게 함으로써, 배열의 각 요소는 이전 요소들의 누적 합으로 업데이트

예를 들어:

• 첫 번째 루프 후 nums 배열은 [1, 2, 3, 4, 5]
• 두 번째 루프 후 nums 배열은 [1, 3, 6, 10, 15]
• 세 번째 루프 후 nums 배열은 [1, 4, 10, 20, 35]

 

 

예를 들어, n = 5이고 k = 3인 경우를 설명

1. 처음에 배열 nums는 [1, 1, 1, 1, 1]
2. k = 3일 때, while 루프가 3번 실행.

첫 번째 루프 (k = 3):

• sum을 0으로 초기화합니다.
• 배열을 순회하면서 sum을 업데이트하고 각 요소를 sum 값으로 설정:
  • i = 0: sum = 0 + 1 = 1, nums[0] = 1
  • i = 1: sum = 1 + 1 = 2, nums[1] = 2
  • i = 2: sum = 2 + 1 = 3, nums[2] = 3
  • i = 3: sum = 3 + 1 = 4, nums[3] = 4
  • i = 4: sum = 4 + 1 = 5, nums[4] = 5
• 첫 번째 루프 후 nums는 [1, 2, 3, 4, 5]
• k는 2로 감소.

두 번째 루프 (k = 2):

• sum을 0으로 초기화.
• 배열을 순회하면서 sum을 업데이트하고 각 요소를 sum 값으로 설정:
  • i = 0: sum = 0 + 1 = 1, nums[0] = 1
  • i = 1: sum = 1 + 2 = 3, nums[1] = 3
  • i = 2: sum = 3 + 3 = 6, nums[2] = 6
  • i = 3: sum = 6 + 4 = 10, nums[3] = 10
  • i = 4: sum = 10 + 5 = 15, nums[4] = 15
• 두 번째 루프 후 nums는 [1, 3, 6, 10, 15]
• k는 1로 감소.

세 번째 루프 (k = 1):

• sum을 0으로 초기화.
• 배열을 순회하면서 sum을 업데이트하고 각 요소를 sum 값으로 설정:
  • i = 0: sum = 0 + 1 = 1, nums[0] = 1
  • i = 1: sum = 1 + 3 = 4, nums[1] = 4
  • i = 2: sum = 4 + 6 = 10, nums[2] = 10
  • i = 3: sum = 10 + 10 = 20, nums[3] = 20
  • i = 4: sum = 20 + 15 = 35, nums[4] = 35
• 세 번째 루프 후 nums는 [1, 4, 10, 20, 35].
• k는 0으로 감소하고 루프를 종료.

결과:

• 마지막 배열 nums는 [1, 4, 10, 20, 35].
• nums[n - 1]은 nums[4]이고, 값은 35