자소서 다듬고, 1,2차 면접 준비하느라 알고리즘에 신경을 못쓰다가 오랜만에 문제 풀었는데, 실력 많이 떨어진 것을 많이 느꼈다.
처음에 이 문제를 풀었을 때, 1번째 스티커를 뜯을 때, 2번째 스티커를 뜯을 때만 고려하면 되는 줄 알았는데, 그 다음에서도 어떤 스티커를 뜯어야 할 지 고민을 해야했다. 아이디어를 구현 못해서 해당링크를 참조했다.
1. 요약
숫자가 적힌 스티커가 원형으로 연결되어있는데, 스티커를 뜯을 경우 양쪽으로 인접한 스티커는 찢어져서 사용할 수 없게된다. 이 때, 스티커들을 뜯고, 여기에 적힌 숫자들의 최대 합을 구해보자.
2. 아이디어
1번째 스티커를 사용할 때, 1번째 스티커를 사용하지 않을 때를 고려한다. 왜냐하면, 1번째 스티커를 뜯게 되면 2번째 스티커를 사용할 수 없기 때문이다. 그런데 결과는 2번째 스티커를 뜯는게 더 큰 결과를 얻을 수 있다. 따라서 초기에, 위의 2가지의 경우를 고려한다.
다음 해야할 일은 어떤 스티커를 뜯을지 고민하는 것이다. 예를들어 1번째 스티커를 뜯었을 때, 다음으로 3번째 스티커를 뜯어낼 지, 4번째 스티커를 뜯어낼 지 고민하는 것이다. 스티커를 뜯어내는 기준은 어떤 것이 가장 큰 값을 만드는데 기여하는 지 여부다. 다시 말해, 4번째 스티커가 3번째 스티커보다 적힌 숫자가 더 클지라도, 조건을 만족하면서 스티커들을 뜯어냈을 때, 3번째 스티커가 더 큰 값에 기여한 경우, 3번째 스티커를 선택해야하는 것이다.
이를 구현하기 위해 DP를 사용한다. 1번째 스티커를 사용할 때, 사용하지 않을 때를 고려한 2차원table을 만들고, i+1번째까지의 스티커들에서 얻을 수 있는 최대 값을 기록한다.(i는 인덱스) 구체적인 방법은 아래와 같다.
table[k][i] = max(sticker[i]+table[i-2], table[i-1])
1번째 스티커를 사용할 때, 사용하지 않을 때 모두 위와 동일하다.(k=0 or 1) 주의해야할 점은 스티커 개수가 1개밖에 없을 때, 변수 초기화, 1번째 스티커를 사용할 때의 end범위 설정이다. 이 부분에 대한 사항은 맨위에 언급된 링크를 참고하면된다.
3. 코드
def solution(sticker):
size = len(sticker)
if size == 1: return sticker[0]
table = [[0 for _ in range(size)] for _ in range(2)]
table[0][0] = sticker[0]
table[0][1] = sticker[0]
table[1][1] = sticker[1]
for i in range(2, size-1): table[0][i] = max(table[0][i-2]+sticker[i], table[0][i-1])
for i in range(2, size): table[1][i] = max(table[1][i-2]+sticker[i], table[1][i-1])
answer = max(table[0][size-2], table[1][size-1])
return answer