[LeetCode] 446. Arithmetic Slices II - Subsequence

https://leetcode.com/problems/arithmetic-slices-ii-subsequence/description/

Arithmetic Slices II - Subsequence - LeetCode

leetcode - Arithmetic Slices II - Subsequence

문제 유형 : 다이나믹 프로그래밍, 해시

문제 난이도 : Hard

 

 

문제

Given an integer array nums, return the number of all the arithmetic subsequences of nums.

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

• For example, [1, 3, 5, 7, 9], [7, 7, 7, 7], and [3, -1, -5, -9] are arithmetic sequences.
• For example, [1, 1, 2, 5, 7] is not an arithmetic sequence.

A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

• For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].

The test cases are generated so that the answer fits in 32-bit integer.

 

정수 배열 nums가 주어진다.

nums의 산술적인 부분순열의 개수를 구하시오.

최소 세 개 이상의 요소들로 이루어져 있는 인접한 숫자들의 차가 모두 같은 부분순열을 산술적이라고 합니다.

테스트 케이스의 답은 32비트 정수 범위 내로 만들어지게 되어있습니다.

 

 

풀이

재귀로 풀어보려고 시도를 했으나.. 한 시간동안 1차원dp로 삽질을 하고 있었다!

오늘 역시 풀이의 도움을 받았다.. 사실 문제만 많이풀었지 실속은 없었나 싶기도 하다.

 

dp[i][diff]를 i번째 요소를 마지막으로 넣은 간격 diff짜리의 값이라고 계산한다.

2차원 배열을 다음과 같이 순회한다:

i = 0 ~ n-1

j = 0 ~ i-1

각 인덱스 i, j의 수의 차이를 구한다.

dp[i][diff]에 우선 1을 추가한다. nums[j], nums[i]순의 길이가 2짜리인 diff의 새로운 부분순열을 하나 생성하는 의미이다.

만약 j로 끝나고 diff의 간격을 두는 부분순열이 있다면, dp[i][diff]에 dp[j][diff]를 더한다.

이 때 dp[j][diff]의 값을 누적 합에도 구한다. 이 때부터는 부분순열의 구성원이 셋 이상이기 때문이다.

 

코드

C++

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        int total_count = 0;

        vector<unordered_map<int, int>> dp(n);

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                long long diff = static_cast<long long>(nums[i]) - nums[j]; 

                if (diff > INT_MAX || diff < INT_MIN)
                    continue; 

                int diff_int = static_cast<int>(diff);

				// nums[j], nums[i]로 시작(i: j야 나랑 부분순열 시작하자)
                dp[i][diff_int] += 1; 
				
                // 만약에 같은 diff로 이어지던 게 있다면, 경우의 수 누적. 여기서는 요소가 3개 이상이므로 총합에 더해도 됨
                if (dp[j].count(diff_int)) {
                    dp[i][diff_int] += dp[j][diff_int];
                    total_count += dp[j][diff_int];
                }
            }
        }

        return total_count;
    }
};