2020-01-15] Get Maximum in Generated Array

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/581/week-3-january-15th-january-21st/3605/

Explore - LeetCode

 

간만에 기분좋게 문제를 풀어 마음이 좋구만. 예시를 보며 문제를 파악해보자.

 

<문제 예시 1-3>

 

입력값 n이 주어지고, 이를 n+1개의 배열에 아래와 같은 rule로 배열 값을 채운다.

rule)

   1) 0번째, 1번째 값은 각 0,1이다.

   2) 2번째 부터 짝수 번째  i 의 값은   nums[2*i]=nums[i]

   3) 2번째 부터 홀수 번째  i 의 값은   nums[2*i+1]=nums[i]+ nums[i+1]

 

이후 채워진 배열에서 가장 큰 원소 값을 반환해준다.

 

문제 풀이)

 

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        nums=[0 for i in range(n+1)] # 최초 주어진 n+1 만큼의 배열 선언
        i=0;
        while i <= n:
            if i == 0: # rule 1-1) 0번째 값은 0
                nums[i]=0
            if i == 1: # rule 1-2) 1번째 값은 1 
                nums[1]=1
            if i%2==0: # rule 2) 2번째부터 짝수 값은  i를 2로 나눈  i/2 번째의 nums 값과 동일
                nums[i]=nums[int(i/2)]
            else: # rule 3) 2번째부터 홀수 값은  i를 2로 나눈  i/2 번째의 nums 값 + (i/2)+1번째 값
                nums[i]=nums[int(i/2)]+nums[int(i/2)+1]
            i+=1
        return max(nums) # 채워진 배열에서 가장 큰 값 반환