프로그래머스 - Summer coding 온라인 예선 3번

5월 20일 오후 한시에 있었던 스타트업 인턴 채용을 위한 대회인 Summer coding 온라인 예선에 참가하게 되었고 문제와 해답을 공유 합니다. 제가 공유한 코드는 전부 만점이긴 하지만, 대회라는 시간이 촉박한 상황에서 작성 했기 때문에 다소 지저분한 코드가 있을 수 있습니다.

문제

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

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

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

제한 사항

•sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.

•sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.

•원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

입출력 예 

sticker	answer
[14, 6, 5, 11, 3, 9, 2, 10]	36
[1, 3, 2, 5, 4]	8

입출력 예 설명

입출력 예 #1

6, 11, 9, 10이 적힌 스티커를 떼어 냈을 때 36으로 최대가 됩니다.

입출력 예 #2
3, 5가 적힌 스티커를 떼어 냈을 때 8로 최대가 됩니다.

풀이

간단한 동적 계획법 문제인데, 가장 코드가 마음에 안드는 문제.

처음 스티커를 제거하면 마지막 스티커를 획득 못하고, 마지막 스티커를 제거하면 처음 스티커를 획득 하지 못합니다.

이 조건 처리가 상당히 귀찮아서 캐싱 배열을 두배로 잡았습니다

처음 스티커를 획득하면 b = 0 / 아닌 경우는 b=1을 넣어서 호출합니다.

s번째 스티커를 때는 경우 = d[s+2] + sticker[s]

s번째 스티커를 안때는 경우 = d[s+1]

s번째 부터 끝까지 스티커를 때서 얻을 수 있는 최댓값 = max ( d[s+2] + sticker[s], d[s+1] )

* 마지막 스터커 처리는 기저 조건에서 처음 스티커를 땠으면 마지막 스티커를 획득 못하게 합니다.

int d[100001][2],len;

int dp(const vector<int>&sticker, int s, int b)

{

    if(s>=len) return 0;

    if(s==len-1)

    {

        if(b==0)return sticker[s];

        else return 0;

    }

    int &ret= d[s][b];

    if(ret != -1) return ret;

    

   return ret = max(sticker[s]+dp(sticker,s+2,b)  , dp(sticker,s+1,b));    

}

int solve(const vector<int>&skicker)

{

    len =sticker.size();

    memset(d,-1,sizeof(d));

    return max(dp(sticker, 2, 1 ) + sticker[0] , dp(sticker,1,0));

}

int solution(vector<int> sticker)

{

    int answer = solve(sticker);

    return answer;    

}