문제

You are given a 0-indexed array of n integers differences, which describes the differences between each pair of consecutive integers of a hidden sequence of length (n + 1). More formally, call the hidden sequence hidden, then we have that differences[i] = hidden[i + 1] - hidden[i].

You are further given two integers lower and upper that describe the inclusive range of values [lower, upper] that the hidden sequence can contain.

For example, given differences = [1, -3, 4], lower = 1, upper = 6, the hidden sequence is a sequence of length 4 whose elements are in between 1 and 6 (inclusive).
[3, 4, 1, 5] and [4, 5, 2, 6] are possible hidden sequences.
[5, 6, 3, 7] is not possible since it contains an element greater than 6.
[1, 2, 3, 4] is not possible since the differences are not correct.
Return the number of possible hidden sequences there are. If there are no possible sequences, return 0.

문제(번역)

당신에게는 정수 배열 differences가 주어지며, 이 배열은 길이 (n + 1)인 어떤 숨겨진 수열(hidden sequence)의 연속된 원소 쌍 간의 차이를 나타냅니다. 더 구체적으로 말하면, 숨겨진 수열을 hidden이라 할 때, 다음과 같은 관계가 성립합니다:

differences[i] = hidden[i + 1] - hidden[i]

또한, 숨겨진 수열의 원소들이 포함될 수 있는 값의 범위를 나타내는 두 정수 lower와 upper가 주어집니다. 이 범위는 [lower, upper] (양 끝값 포함)입니다.

예를 들어, differences = [1, -3, 4], lower = 1, upper = 6이 주어졌다면, 숨겨진 수열은 길이 4이며 모든 원소가 1 이상 6 이하의 값이어야 합니다.
예를 들면:
• [3, 4, 1, 5]와 [4, 5, 2, 6]은 가능한 숨겨진 수열입니다.
• [5, 6, 3, 7]은 7이 범위 초과이므로 불가능합니다.
• [1, 2, 3, 4]는 differences 값이 일치하지 않으므로 불가능합니다.

가능한 숨겨진 수열의 개수를 반환하세요.
가능한 수열이 없다면 0을 반환합니다.

예제

예제 1

입력 : differences = [1, -3, 4], lower = 1, upper = 6
출력 : 2
설명 : 가능한 숨겨진 수열은 다음과 같다.

• [3, 4, 1, 5]
• [4, 5, 2, 6]
  따라서 가능한 수열의 개수는 2이므로 2를 반환한다.

예제 2

입력 : differences = [3, -4, 5, 1, -2], lower = -4, upper = 5
출력 : 4
설명 : 가능한 숨겨진 수열은 다음과 같다.

• [-3, 0, -4, 1, 2, 0]
• [-2, 1, -3, 2, 3, 1]
• [-1, 2, -2, 3, 4, 2]
• [0, 3, -1, 4, 5, 3]
  따라서 가능한 수열의 개수는 4이므로 4을 반환한다.

---

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        current = 0
        prefix_sums = [0]
        
        for diff in differences:
            current += diff
            prefix_sums.append(current)
        
        min_val = min(prefix_sums)
        max_val = max(prefix_sums)
        
        # 시작 숫자가 x라면,
        # x + min_val >= lower
        # x + max-val <= upper
        # x >= lower - min_val
        # x <= upper - max_val
        
        min_start = lower - min_val
        max_start = upper - max_val
        
        if max_start < min_start:
            return 0
        return max_start - min_start + 1

로직

differences[i] = hidden[i+1] - hidden[i]

• differences = [1, -3, 4]이 주어진다면,
  • hidden[1] = hidden[0] + 1
  • hidden[2] = hidden[1] - 3 = hidden[0] + 1 - 3
  • hidden[3] = hidden[2] + 4 = hidden[0] + 1 - 3 + 4

이런식으로 이어지게 된다.
즉, hidden 수열 전체는 hidden[0]을 기준으로 아래와 같이 표현된다.
hidden = [x, x+1, x+1-3, x+1-3+4]

그 후에 current를 누적하며 저장하면, hidden 수열의 나머지 값들이 어떤 상대적 위치에 있는지 알 수 있다.

hidden 수열의 모든 값은 [lower, upper] 범위안에 있어야 하므로,
x + min(prefix_sums) >= lower
x + max(prefix_sums) <= upper
을 만족해야만 한다.

lower - min(prefix_sums) <= x <= upper - max(prefix_sums)

이렇게 정리하여 x(시작값)이 될 수 있는 범위를 정할 수 있다.

시작 숫자가 x라면,
x + min_val >= lower
x + max-val <= upper
x >= lower - min_val
x <= upper - max_val

differences = [1, -3, 4], lower = 1, upper = 6을 예시로 든다면

• prefix_sums = [0, 1, -2, 2]
• min_val = -2
• max_val = 2
• 가능한 시작값 x 범위는:
  • x >= lower - min_val = 1 - (-2) = 3
  • x <= upper - max_val = 6 - 2 = 4
• 따라서 x = 3 또는 4일 때만 가능 → 정답: 2