사용자 도구

사이트 도구


ps:problems:programmers:12971

스티커 모으기(2)

ps
링크https://programmers.co.kr/learn/courses/30/lessons/12971
출처프로그래머스
문제 번호12971
문제명스티커 모으기(2)
레벨Level 4
분류

동적계획법

시간복잡도O(n)
인풋사이즈n<=100,000
사용한 언어Python
해결날짜2020/12/19
  • 같은 프로그래머스 사이트에 있는, 도둑질과 동일한 문제이다.
  • 문제 이름이 스티커 모으기(2) 인데, 정작 스티커 모으기(1)은 사이트에서 찾을 수가 없다.

풀이

  • 도둑질 참고
  • 이 문제가 도둑질과 유일하게 다른 점은, n이 1인 경우도 인풋으로 올수 있기 때문에, 그 경우의 처리만 해줘야 한다는 것. 그것을 제외하고는 코드도 모두 동일하다
    • 저 처리를 빼먹으면, 33번 테스트 케이스에서 실패한다.

코드

"""Solution code for "Programmers 12971. 스티커 모으기(2)".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12971
- Solution link: http://www.teferi.net/ps/problems/programmers/12971
"""


def solution(sticker):
    if len(sticker) == 1:
        return sticker[0]
    dp1, dp1_cur = [0, sticker[0]], max(sticker[0], sticker[1])
    dp2, dp2_cur = [0, 0], sticker[1]
    for m in sticker[2:]:
        dp1[-1], dp1[-2] = dp1_cur, dp1[-1]
        dp2[-1], dp2[-2] = dp2_cur, dp2[-1]
        dp1_cur = max(dp1[-1], dp1[-2] + m)
        dp2_cur = max(dp2[-1], dp2[-2] + m)
    return max(dp1[-1], dp2_cur)

토론

댓글을 입력하세요:
C X N M B
 
ps/problems/programmers/12971.txt · 마지막으로 수정됨: 2021/01/21 15:32 저자 teferi