[프로그래머스(Programmers)][자바(java)] (Lv3) 스티커 모으기(2)

 

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

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

 

문제 풀이

*  동적 계획법

• 원형의 스티커판을 입력받은 배열대로 직선으로 늘여놓고 보자
• 첫 번째 스티커를 뗀다고 가정하면 두 번째 스티커와 맨 끝 스티커는 뗄 수 없다. 또한 첫 번째 스티커를 떼지 않는다면 맨 끝 스티커를 뗄 수 있다.
  ( 스티커의 개수를 n개라고 할 경우, n-1 번째가 맨 끝 )
• 따라서 첫 번째 스티커를 떼는 경우와 떼지 않는 경우를 두 가지로 나누고 int sticker[] 배열 탐색
  -  첫 번째 스티커를 떼는 경우  --   0 ~ n-2 번째 까지 탐색
  -  첫 번째 스티커를 떼지 않는 경우  --  1 ~ n-1 번째 까지 탐색
  -  배열은 탐색하는 시작 인덱스와 끝 인덱스를 각각 int s, e 에 담음 

	s	e
첫 번째 스티커를 떼는 경우	0	n-2
첫 번째 스티커를 떼지 않는 경우	1	n-1

• 위의 두 경우 안에서, 배열을 탐색하며 i번째 스티커를 떼는 경우와 안 떼는 경우 얻을 수 있는 값이 각기 다르므로 2*n 크기의 int dp[][] 배열을 생성하여 s ~ i번째 스티커까지 얻을 수 있는 최댓값을 저장
  -  dp[0][i]  :  i 번째 스티커를 뗄 경우  ☞  max( dp[0][i-2], dp[1][i-2] ) + sticker[i]
  -  dp[1][i]  :  i 번째 스티커를 떼지 않을 경우  ☞  max( dp[0][i-1], dp[1][i-1] )
  -  s ~ e까지의 범위에서 얻을 수 있는 최댓값은 max( dp[0][n-1], dp[1][n-1] )
• 최종 최댓값 return

public class Solution {
	
	public int solution(int sticker[]) {
		int n = sticker.length, max = 0, i, j, s = 0, e = n-2, dp[][];
		if( n == 1 ) return sticker[0];
		for( j = 0; j < 2; j++ ) {
			dp = new int[2][n];
			for( i = s; i <= e; i++ ) {
				dp[0][i] = ( i >= 2 ? Math.max( dp[0][i-2], dp[1][i-2] ) : 0 ) 
					   + sticker[i];
				dp[1][i] = i >= 1 ? Math.max( dp[0][i-1], dp[1][i-1] ) : 0;
			}
			max = Math.max( max, Math.max( dp[0][e], dp[1][e] ) );
			s++; e++;
		} 
		return max;
	}
}