1646. Get Maximum in Generated Array (생성된 배열에서 최대값 가져오기)

정수 n이 주어집니다. 길이 n + 1의 0 인덱스 정수 배열 수는 다음과 같은 방식으로 생성됩니다:

• nums[0] = 0
• nums[1] = 1
• nums[2 * i] = nums[i] when 2 <= 2 * i <= n
• nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n

배열 nums의 최대 정수를 반환합니다.

 

 

예시 1:

입력: n = 7
출력: 3
설명: 주어진 규칙에 따라:
nums[0] = 0
nums[1] = 1
nums[(1 * 2) = 2] = nums[1] = 1
nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
nums[(2 * 2) = 4] = nums[2] = 1
nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
nums[(3 * 2) = 6] = nums[3] = 2
nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
이런 이유로, nums = [0,1,1,2,1,3,2,3], 그리고 최대값은 max(0,1,1,2,1,3,2,3) = 3입니다.

 

예시 2:

입력: n = 2
출력: 1
설명: 주어진 규칙에 따르면 nums = [0,1,1]입니다. 최대값은 max(0,1,1) = 1입니다.

 

예시 3:

입력: n = 3
출력: 2
설명: 주어진 규칙에 따르면 nums = [0,1,1,2]입니다. 최대값은 max(0,1,1,2) = 2입니다.

 

 

조건:

• 0 <= n <= 100

 

정답:

public class Solution {
    public int GetMaximumGenerated(int n) {
        List<int> result = new List<int>();

        if (n >= 0)
        {
            result.Add(0);
        }
        if (n >= 1)
        {
            result.Add(1);
        }
        
        for (int i = 1; i * 2 <= n; i++)
        {
            result.Add(result[i]);

            if (i * 2 + 1 <= n)
            {
                result.Add(result[i] + result[i + 1]);
            }
        }

        return result.Max();
    }
}

해설: n이 0이상일 경우 0을 추가하고 마찬가지로 1이상일 경우 1도 추가합니다.

그 이후 i * 2가 n이하일 경우 규칙에 따라 result[i]를 추가하고 i * 2 + 1 또한 n이하일 경우에 result[i]와 방금 추가한 result[i + 1]를 더한 값을 추가해줍니다.

해당 작업을 반복 한 후 result의 최대값을 return해줍니다.