티스토리 뷰

저는 가금 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


라고 적혀 있긴 하지만 읽어봐도 이해가 되지 않습니다.

혹시 설명이 가능하신분 있나요? ^^;;

댓글
  • 프로필사진 skrmsp (1) : 1, 4
    (2) : 11, 41, 14, 44, 2 = (1)1, (1)4, 2
    (3) : (2)1, (2)4, (1)2, 3
    (4) : (3)1, (3)4, (2)2, (1)3
    (5) : (4)1, (4)4, (3)2, (2)3

    (n-1)1, (n-1)4, (n-2)2, (n-3)3 으로 모든 순열 조합이 만들어 지네요. 절묘하군요...
    이런걸 증명하려면 수학의 어느 분야를 공부해야 할까요?
    2007.05.25 18:38
  • 프로필사진 Favicon of http://mastojun.net BlogIcon Mastojun 아...
    이제 이해 됬습니다 ^^;; 감사합니다.

    무슨분야랑 관련있는지는 수학도가 아니라 모르겠고 @_ @);;;
    2는 1과의 차이가 1이기 때문에 1을 만드는 목록에다 1을 하나씩 추가하고, 4는 1과 같은값이므로 4도 하나씩 추가하고, 마지막으로 2를 하나 추가.
    3은 1과의 차이가 2이기 때문에 1을 만드는 목록에다 2를 하나씩 추가하고, 2와의 차이는 1이기 때문에 2를 만드는 목록에다 1을 하나씩 추가하고, 4를 하나씩 추가하고 그리고 3을 더하고..

    이런식이였군요.,,..
    2007.05.25 20:57
댓글쓰기 폼