코딩테스트 -- 스티커 모으기(2) - (프로그래머스 / C++)

프로그래머스

 

문제!

---

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

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

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

 

 

---

요약하면 스티커를 떼어낸 합의 최댓값을 구하는 문제로 

 

1. 스티커를 떼면 양쪽 스티커를 사용하지못함
2. 처음과 끝이 이어져 있음

이렇게 2개의 조건을 지켜 푸는 문제입니다!

 

 

 

어느것을 떼어 내야할까.... 고민을 해보았지만 

 

완전탐색을 통한 방법  >> 스티커가 100,000 개...

특정 공식이 있는지? >> 못 찾겠습니다...

 

 

하지만 식을 찾던 도중

 

특정위치에 스티커의 합을 누적해서 처리해준다?  >>  DP!

모든 위치에 대해서 메모이제이션을 통해 값을 정해주고 최신화 시켜주어 최댓값을 구할 수 있겠다고 생각하여!

 

아래처럼 모든 부분을 수정하고 마지막 값을 출력했습니다. (dp의 점화식!)

memo[i] = max(memo[i - 2] + sticker[i], memo[i - 1])

 

해서 풀어 보았지만 바로 틀렸네요 ㅋㅋ

 

 

여기서는 조금 찾아 보았습니다.

 

먼저 dp를 이용하는 문제는 맞았습니다! 와!

그런데 여기서 한가지를 더 생각 했어야했습니다...

 

조건 2.처음과 끝이 이어져 있음

 

연결되어 있기에 0번 스티커를 떼어내는 경우, 안 떼어내는 경우 이렇게 2가지로 나누어 생각했어야 했네요;;

 

 

 

 

 

코드 시작!

---

 

먼저 모든 스티커값을 저장해줄 메모 선언 , 스티커가 한장일때의 경우 처리

 int memo[100001];
 
 if (sticker.size() == 1){
        return sticker[0];
    }

 

그리고 첫번째 스티커를 뜯는 부분부터 먼저 생각해줍시다.

    //첫번째 스티커를 뜯는 부분
    memo[0] = sticker[0];//
    memo[1] = sticker[0];//첫번째를 뜯었으므로 두번째는 못뜯는다는점! 기억
    
    for (int i = 2; i < sticker.size() - 1; i++){  
        memo[i] = max(memo[i - 2] + sticker[i], memo[i - 1]);// 현재위치를 뗄지 안뗄지
    }
    
    answer = max(answer, memo[sticker.size() - 2]);

첫번째를 뜯어버리면 두번째와 제일끝 스티커를 생각하지 않아도 되므로

두번째= 첫번째

제일끝은 생각하지 말아줍시다.

 

 

 

이번엔 첫번째를 안뜯는 경우

//첫번째 스티커를 안뜯는 부분
    memo[0] = 0;
    memo[1] = sticker[1];
    for (int i = 2; i < sticker.size(); i++){ 
        memo[i] = max(memo[i - 2] + sticker[i], memo[i - 1]);// 현재위치를 뗄지 안뗄지
    }    
    
    answer = max(answer, memo[sticker.size() - 1]);

이 경우에서는 첫번째를 0으로 선언해주고 

2번째를 뜯어낸걸로 시작해주시면 됩니다!

 

 

어렵네요....

 

끝!

 

ALL

#include <iostream>
#include <vector>

using namespace std;



int solution(vector<int> sticker){    
    int answer = 0;   
    
    int memo[100001];   
    
    if (sticker.size() == 1){
        return sticker[0];
    } 
    
    //첫번째 스티커를 뜯는 부분
    memo[0] = sticker[0];//
    memo[1] = sticker[0];//첫번째를 뜯었으므로 두번째는 못뜯는다는점! 기억
    
    for (int i = 2; i < sticker.size() - 1; i++){  
        memo[i] = max(memo[i - 2] + sticker[i], memo[i - 1]);// 현재위치를 뗄지 안뗄지
    }
    
    answer = max(answer, memo[sticker.size() - 2]);
    
    
    //첫번째 스티커를 안뜯는 부분
    memo[0] = 0;
    memo[1] = sticker[1];
    for (int i = 2; i < sticker.size(); i++){ 
        memo[i] = max(memo[i - 2] + sticker[i], memo[i - 1]);// 현재위치를 뗄지 안뗄지
    }    
    
    
    
    answer = max(answer, memo[sticker.size() - 1]);    
    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!