컴퓨터는 재귀를 사랑해

프로그래머스 「Summer/Winter Coding(~2018) 스티커 모으기(2)」 문제

프로그래머스

 

 

재귀적으로 생각할 때 중요한 것은 꺾이지 않는 마음 $i$번째의 결과와 $(i - 1)$번째 결과와의 관련성이다.

 

해당 문제의 경우 $i\geq 2$일 때 $i$번째 점수는

1. $(i - 2)$번째 점수 + sticker[$i$](choose case) 또는

2. $(i - 1)$번째 점수(pass case)

중에서 큰 것이었다.

 

내가 해당 알고리즘을 고려하지 못한 주요한 이유는 기본 예시에서 4번째 점수가 14, 11 조합인 25점이 나와야 하지만 실제로 그럴 수 없을 것이라고 생각했기 때문이다. 하지만

1. choose(14) pass(14) pass(14) choose(25) 조합으로  실제로 나올 수 있고

2. 해당 점수가 안 나온 것은 내 코딩이 틀렸기 때문이었다.