simbaddaji   8달 전

테스트 케이스는 맞는데 어느 부분이 잘 못 됐는지 잘 모르겠어요.

alphago92   8달 전

1이 100번 입력되었을때의 값이

정답코드와 다르게 나옵니다


이 문제를 dp로 푸는 핵심은

만들어내는 값이 음수여서도 안되고 20을 넘어서도 안된다는 겁니다

즉 항상 값이 0~20 사이이므로 크기 21짜리 1차원 배열을 만들면 편할 겁니다

그 배열을 result[21]이라고 합시다


dp를 많이 풀어보시면 감이 오겠지만

예컨대 result[10] 은 10이 만들어지는 경우의 수 입니다

숫자를 하나씩 읽어옵니다.

만약 숫자가 2인경우에 result[n] 은 

result[n-2] + result[n+2] 가 되겠지요 (물론 배열의 index범위를 넘어가는지 검사해줘야합니다)

그전까지 8을 완성하는 식에 +2 를 하면 10이 완성이되고

그전까지 12를 완성하는 식에 -2 를 해도 10이 완성이 되기 때문입니다

참고하시길바랍니다

댓글을 작성하려면 로그인해야 합니다.