알고리즘 분류는 solved.ac 에서 유저들의 투표로 이루어지므로 문제의 의도를 결정하는 요소가 될 수 없습니다. 단순히 "dp를 하지 않고도 통과가 되었기 때문에" dp 태그를 투표하지 않더라도 분류에 안 붙게 됩니다.
그것보다 이 문제에 dp 분류를 붙이지 않는 이유는 문제가 dp라고 생각할 필요도 없을 정도로 쉽기 때문입니다. 문제에 나온 그대로 순서대로 답을 구하면 되므로 dp의 관점에서 문제를 풀 필요가 없기에 dp 태그를 대부분 투표하지 않는 것입니다.
하지만 이 문제를 평범한 재귀로 구현했다면 그건 매우 비효율적인 풀이가 됩니다. 그를 다시 효율적으로 만들기 위해서는 메모이제이션을 해야 한다는 것이지, 그것이 정해이기 때문에 정해대로 풀지 않은 코드를 통과시키지 말자는 의미는 아닙니다. 다만 그냥 재귀를 돌리는 풀이가 매우 비효율적이고, 그 풀이가 특정 언어에서만 시간 보너스 때문에 가까스로 통과된다면 통과가 의도된 것이라고 보기 어려우며, 구현상에서의 약간의 효율성 차이만으로도 통과 여부가 갈릴 수 있기 때문에 이러한 풀이를 완전히 막거나 완전히 통과시키거나를 하는 것이 좋다고 봅니다. 이 문제가 매우 오래된 문제임을 감안하면 처음 문제가 나왔을 때에는 컴퓨터의 성능이 지금처럼 좋지 않아 절대로 이러한 풀이가 통과될 수 없었을 것입니다. 그렇기 때문에 이러한 풀이가 통과를 의도하지 않았다고 생각하며, 이를 막기 위해 시간 제한을 조정하는 것은 이 의도를 살리는 좋은 방법이라고 생각합니다.

djm03178 5년 전
메모이제이션을 사용하지 않고 재귀를 수행하는 PyPy3 코드가 아슬아슬하게 통과됩니다. https://www.acmicpc.net/source...
큰 케이스를 더 많이 포함하는 데이터를 추가하거나 시간 제한을 많이 줄여주세요.