프로그래머스 스티커 모으기(2)

🙂 문제 - 스티커 모으기(2)

url : https://programmers.co.kr/learn/courses/30/lessons/12971

✔️ 문제 내용

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.
예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.해주세요.

❌ 제한 사항

• sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.
• sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.
• 원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

🖐풀이 방법

• 프로그래머스에서 LEVEL 2로 되어있다.
• 먼저 제한사항에 N의 길이가 100000이하임으로 완전 탐색은 되지 않는다
• 순차적으로 수를 더하는 것이기에 DP 방법을 사용하려 한다.
• dp 배열에 각 index에 해당하는 것은 스티커 순번이고 값은 스티커가 무조건 띄어졌다 라는 가정으로 문제를 풀 예정인다.
• 이때 일반적인 DP와 달리 맨 마지막과 맨 처음의 연관성이 있다.
• 그래서 맨 처음스티커를 떼었다고 가정한 배열과 떼지 않았다고 가정한 배열 두개로 계산한다.
• 맨 처음 스티커를 뗀 배열에서는 맨 마지막 스티커를 연산하지 않아준다.
• 추가로 배열 크기가 1일 때는 그냥 스티커 하나를 무조건 떼는게 좋음으로 연산 없이스티커 값을 리턴한다.
• off_zero[2]의 뜻은 첫번째 스티커를 떼지 않은 경우에 세번째 스티커를 뗄것인가 말것인가 라는 가정으로 푸는 것이다.
• on_zero[2]의 뜻은 첫번째 스티커를 뗀 경우에 세번째 스티커를 뗄것인가 말것인가 라는 가정으로 푸는 것이다.
• 수식은
  (자신의 전전까지의 값+ 자신의 값) - 자신을 뜯음 과
  (자신의 전 값) - 자신을 뜯지 않음
  중 큰것으로 하면 된다.

📃 CODE

 def solution(sticker):
   answer = 0
   
   if len(sticker)==1:
       return sticker[0] # 스티커 하나일 때
       
   off_zero = [0 for i in sticker] # 0번째 스티커를 떼지 않았을 때 배열
   on_zero = [0 for i in sticker] # 0번째 스티커를 떼었을 때 배열
   
   # 값 초기화 이 때 0번째 스티커를 떼지 않는 배열에서는 0번째 값을 0으로 한다.
   on_zero[0],on_zero[1]=sticker[0],sticker[0] 
   off_zero[1],off_zero[0]= sticker[1],0
   
   
   for idx in range(2,len(sticker)):
       off_zero[idx] = max(off_zero[idx-1],off_zero[idx-2]+sticker[idx])
       
       if(idx == len(sticker)-1): # 맨 처음 스티커를 뗀 배열에서는 맨 마지막 스티커를 연산하지 않아준다.
       	continue
           
       on_zero[idx] = max(on_zero[idx-1],on_zero[idx-2]+sticker[idx])
   
   
   return max(max(on_zero),max(off_zero))