프로그래머스. 스티커 모으기(2)

tose33 2023. 7. 31. 13:34

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

i 번째 스티커를 땔지 안땔지로 구분해주면 되는 문제로 점화식 d[i] = max(d[i-2]+a[i], d[i-1]) 이다.

그런데 이 문제는 스티커가 원형 모양으로 되있다.

즉 첫 원소와 마지막 원소를 동시에 땔 수 없다.

따라서 첫 원소를 제외하고 한 번 쭉 계산, 마지막 원소를 제외하고 쭉 계산 해서 최댓값이 정답이된다.