Algorithm/프로그래머스 문제풀이

[프로그래머스] 스티커 모으기(2) - Java

너지살 2022. 5. 25. 21:05

 

문제출저 : 

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

 

코딩테스트 연습 - 스티커 모으기(2)

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록

programmers.co.kr

 

 

 

import java.util.*;

class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
        
        int n = sticker.length;
        
        if(n == 1) return sticker[0];
        
        int[] dp1 = new int[100001]; // 처음을 붙였을 경우
        int[] dp2 = new int[100001];
        dp1[1] = sticker[0];
        
  
        for(int i = 2; i < n; i++)
        {
            dp1[i] = Math.max(dp1[i-2] + sticker[i-1], dp1[i-1]);
        }

        dp2[2] = sticker[1];
        for(int i = 3; i < n+1; i++)
        {
            dp2[i] = Math.max(dp2[i-2] + sticker[i-1], dp2[i-1]);
        }
        
        
        
        answer = Math.max(dp1[n-1], dp2[n]);
        
        return answer;
    }
}