저는 가금 Programming-challenges에 있는 문제를 풀어보고 있습니다. 프로그래밍 실력도 쌓아보고, 알고리즘 설계능력이나 사고력을 증진시켜 보고자 시작한 일이죠.,
그 중에서 counting이라는 문제가 있습니다. ( http://acm.uva.es/p/v101/10198.html ) 나름대로 알고리즘을 생각하고 풀려고 했는데, 입력값이 특정숫자가 넘어가면 기본 자료형으로는 담을 수 없는 크기만큼 값이 늘어나게 됩니다. (적어도 2^1000보단 커지니까요) 혹시 제가 잘못 생각한건 아닌가 해서 ACM게시판을 살짝 뒤져봤는 제대로 생각한것은 맞더군요.,
하지만~ 글을 읽던중에 흥미로운것을 발견했습니다.
저는 단지 for문을 이용해서 숫자를 만들 수 있는 1, 2, 3 의 순열들을 찾아서 계산하는 식으로 알고리즘을 생각했는데, f(n) = 2f(n-1) + f(n-2) + f(n-3) 이라는 공식으로 해결이 된다는 겁니다.
아무리 생각해봐도 저걸 증명할 수 없겠어요 @_ @ 게시판의 설명으로는..
let f(n) denote the no of ways to make numbers with the sum n. The number of ways to make n is the same as the number of ways to make n-1 + no of ways to make n-2 + no of ways to make + no of ways to make n-3 + no of ways to make n-4. However since 4 = 1, it is basically
라고 적혀 있긴 하지만 읽어봐도 이해가 되지 않습니다.
혹시 설명이 가능하신분 있나요? ^^;;
