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

1. 문제

우박수열 정적분

2. 개요

초항 k에 대해 다음과 같은 규칙을 따라 만든 수열을 우박수열이라고 한다.

1-1. k가 짝수라면 2로 나눈다. 1-2. k가 홀수라면 3을 곱하고 1을 더한다.

1. 결과로 나온 수가 1보다 크다면 1을 반복한다.

좌표평면 위에 x = 0, y = k를 시작으로, 다음 항을 x = 1 에 표시하는 방식으로 우박수가 1이 될 때까지 점들을 찍고 인접한 점들을 잇는 꺾은선 그래프를 그릴 수 있다.

이러한 그래프를 이용하여 초항 k와 구간들의 목록이 주어졌을 때, 각 구간들의 정적분의 결과를 리턴하는 문제.

3. 풀이 및 코드

3-1. 풀이

먼저 주어진 초항 k를 시작으로 우박수열을 완성시킨다.

완성된 우박수열로 가로의 길이가 1인 각 구간의 넓이를 구해 리스트에 저장한다.

위 리스트를 통해 0부터 x까지의 넓이의 누적합 리스트를 만든다.

주어진 구간들을 하나하나 탐색하며 누적합 리스트를 참조해 계산하여 답을 리턴한다.

3-2. C#

using System;
using System.Collections;
using System.Collections.Generic;

public class Solution {
    public double[] solution(int k, int[,] ranges) {
        List<int> p = new List<int>() { k };
        List<double> sizes = new List<double>();

        while (k > 1)
        {
            if (k % 2 == 0)
                k /= 2;

            else
                k = k * 3 + 1;

            p.Add(k);

            double size = (double)(p[p.Count - 1] + p[p.Count - 2]) / 2;
            sizes.Add(size);
        }

        double[] accSizes = new double[sizes.Count + 1];

        for (int i = 1; i < accSizes.Length; i++)
            accSizes[i] = accSizes[i - 1] + sizes[i - 1];

        double[] result = new double[ranges.GetLength(0)];

        for (int i = 0; i < ranges.GetLength(0); i++)
        {
            int start = ranges[i, 0];
            int end = sizes.Count + ranges[i, 1];

            if (end < start)
                result[i] = -1;

            else
                result[i] = accSizes[end] - accSizes[start];
        }


        return result;
    }
}