[Algorithm] 프로그래머스 - 우박수열 정적분

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 프로그래머스 dp 문제 중 우박수열 정적분 문제를 해결한 과정을 정리하고자 합니다.

앞 서, 약수를 먼저 구하고 dp를 처리하는 '억억단을 외우자' 문제를 해결한 이후라 비교적 빠르게 해결할 수 있었습니다.

문제 링크는 다음과 같습니다. 

https://school.programmers.co.kr/learn/courses/30/lessons/134239

 

 

 

1. 문제 해결 소스 

 

import java.util.*;

class Solution {
    
    List<Integer> heights = new ArrayList<>();
    
    public double[] solution(int k, int[][] ranges) {
        double[] answer = new double[ranges.length]; // 정답 배열
        heights.add(k); // k를 단계별로 처리한 값을 heights에 넣기 위한 arrayList
        
        while (k > 1) {
            if (k % 2 == 0) k /= 2;
            else {
                k *= 3;
                k++;
            }
            heights.add(k);
        } 
        
        double[] dp = new double[heights.size()]; // dp 선언 

        // 너비 단위는 1 (ranges가 int 이차원 배열이므로), 인덱스 i의 k 와 i - 1의 k로 사다리꼴 넓이 구하기 
        for (int i = 1; i < heights.size(); i++) {
            dp[i] = dp[i - 1] + (heights.get(i - 1) + heights.get(i)) * 1.0 / 2; // 이전 dp를 더함으로써 누적합
        }
        
        int last = heights.size() - 1;
        for (int i = 0; i < ranges.length; i++) {
            int a = ranges[i][0]; // 범위 a 
            int b = ranges[i][1]; // 범위 b 
            
            if (a > heights.size() || (last + b) < a) {  // 정적분되는 실제 범위가 유효하지 않은 경우
                // ex) last : 6, last = -3, a = 4 ==> 양수 정적분 불가 
                answer[i] = -1.0;
                continue;
            }
            
            double total =  dp[last];
            answer[i] = total - dp[a] - (dp[last] - dp[last + b]); // 전체에서 양측 범위에 해당하는 적분 결과 빼서 중간 범위 구하기
        } 
   
        return answer;
    }
}

 

 

 

2. 주의할 점

• 문제에서, 1-1, 1-2로 되어 있는 파트 단계별 순서가 아닌 분기되는 조건이므로 2로 나누었을 때, 홀수가 되더라도 1-1 이후, 1-2로 가는 것이 아니라 2번 스텝으로 가야 합니다.
• 적분 구간이 다소 헷갈릴 수 있었습니다.
  range = [0, 0]이 전구간 적분 결과가 나오는 이유는, a에서 b까지 적분 되는 결과에서 
  range[0]이 의미하는 바는 x = 0에서 range[0]만큼 떨어진 구간이고, 
  range[1]은 x = lastIndex 에서 range[1]만큼 더한 (range[1]이 음수이므로) 범위를 의미합니다. 
  따라서, [0, 0]은 x = 0 - 0 = 0, x = last - 0 = last이므로 전 구간 적분입니다.
• a 에서 b까지 이루어지는 적분에서 만약 a 가 b 보다 큰 경우는 -1.0을 리턴하도록 문제에서 정의되어 있으므로,
  이 부분을 반드시 체크해야합니다.!

 

이상으로 프로그래머스 우박수열 정적분 문제를 마치도록 하겠습니다.

감사합니다.!