[문제풀이] 스티커 모으기2

업데이트:

문제 링크 : 스티커 모으기2

풀이 시간 : 60분

1. 문제 풀이

DP를 이용하여 최대 값을 찾는 문제

원형으로 모양이기 때문에 첫 번째를 사용하는 경우와 안하는 경우로 나워서 최대 값을 찾음

1) 첫 번째 스티커를 무조건 사용한 경우에서 최대 값을 찾음

2) 사용하지 않은 경우에서 최대 값을 찾음

3) 두 경우의 최대 값을 찾음

2. 소스 코드

    public int solution(int sticker[]) {
		int answer = 0;
		// 각 스티커를 사용할 지, 사용했을 때 값은 0번, 사용하지 않았을 때 1번에 인덱스에 저장
		int[][] arr = new int[sticker.length][2];
		if (sticker.length > 2) {//sticker 길이가 1일때 조심 33번 테케
			// 무조건 첫번째를 사용할 때
			arr[1][0] = sticker[0];// 첫번째를 사용하면 두번째를 사용하지 못하기 때문에
			arr[1][1] = sticker[0];
			for (int i = 2; i < arr.length - 1; i++) {
				// 현재 스티커를 사용하면 이전 스티커가 사용하지 않아야기 때문에
				// 이전 스티커를 사용하지 않는 비용인 arr[i-1][1]와 현재 스티커 비용을 더함
				arr[i][0] = arr[i - 1][1] + sticker[i];
				// 사용하지 않을 경우 이전 스티커에서 최대 값을 저장
				arr[i][1] = Math.max(arr[i - 1][0], arr[i - 1][1]);
			}
			//첫번째를 무조건 사용하였기 때문에 마지막 스티커도 사용 불가능
			//그래서 마지막 스티커 전 스티커에서 최대값을 뽑음
			answer = Math.max(arr[arr.length - 2][0], arr[arr.length - 2][1]);
			//첫 번째를 사용 안 할 때
			arr[1][0] = sticker[1];
			arr[1][1] = 0;
			for (int i = 2; i < arr.length; i++) {
				arr[i][0] = arr[i - 1][1] + sticker[i];
				arr[i][1] = Math.max(arr[i - 1][0], arr[i - 1][1]);
			}
			// 첫번째를 사용 안하기 때문에 마지막 스티커에서 최대값 선택
			answer = Math.max(answer, Math.max(arr[arr.length - 1][0], arr[arr.length - 1][1]));
		}else {
			answer = sticker[0];
		}
		return answer;
	}

3. 후기

원형이라서 첫 번째의 경우를 처리하는 방법이 떠오르지 않아서

사용할 때와 사용하지 않는 경우를 나눠서 두 가지의 경우를 다 돌렸다

나중에 시간이 되면 한 번에 처리하는 경우를 생각할 예정이다

아래 주의를 생각하지 못해서 시간이 오래걸렸다.

4. 주의

스트커의 길이가 1인 경우를 처리하지 않아서 계속 33번이 틀렸다.

길이가 1인 경우 처음 초기 값 세팅을 할 때 인덱스의 범위를 벗어나서 계속 틀렸다고 나온다(33번 케이스)

참고