3개의 댓글이 있습니다.
-
-
neoevoke -
문제를 생각하기 편하게 조금 바꿔서
f(n,m)=숫자 n을 m이하의 수로 더해서 만드는 경우의 수로 바꿔도 같겠죠?
그렇게 해서 직접 잘라보시면
참고로
2 = 1 1 f(2,1)
3 = 1 1 1 f(3,1) = 1
= 2 1 f(3,2) = f(3,1)+f(1,1)
4 = 1 1 1 1 f(4,1) = f(3,1)
= 2 1 1 f(4,2)
= 2 2 f(4,2) = f(4,1)+f(2,2)
= 3 1 f(4,3) = f(4,2)+f(1,1)
5 = 1 1 1 1 1 f(5,1) = f(4,1)
= 2 1 1 1 f(5,2)
= 2 2 1 f(5,2) = f(5,1)+f(3,2)
= 3 1 1 f(5,3)
= 3 2 f(5,3) = f(5,2)+f(2,2)
= 4 1 f(5,4) = f(5,3)+f(1,1)
6 = 1 1 1 1 1 1 f(6,1) = f(5,1)
= 2 1 1 1 1 f(6,2)
= 2 2 1 1 f(6,2)
= 2 2 2 f(6,2) = f(6,1)+f(4,2)
= 3 1 1 1 f(6,3)
= 3 2 1 f(6,3)
= 3 3 f(6,3) = f(6,2)+f(3,3)
= 4 1 1 f(6,4)
= 4 2 f(6,4) = f(6,3)+f(2,2)
= 5 1 f(6,5) = f(6,4)+f(1,1)
이렇게 쫙 적어놓으면
뭔가 웬지 규칙을 발견할 수 있을 것만 같지 않나요?
참고로
f(1,1)=1
f(2,2)=1 1
=2
f(3,3)=1 1 1
2 1
3
즉, f(n,n)=f(n,n-1)+1 임을 알 수 있습니다.
그래서 f(n,m)=f(n,m-1)+f(n-m,min(m,n-m))을 유도 할 수 있습니다.
14년 전 link
-
-
-
wookayin -
규칙....으로 찾는건 동적계획법 공부에 도움이 별로 안되니까 잘 생각해보죠.
f(n,m) = n길이의 막대를 m이하의 막대를 사용하여 자르는 경우의 수
n = 1 이거나 m = 1 이면 자명하게 f(n, m) = 1
n < m 이면 f(n, m) = f(n, n). 당연하죠?
n = m > 1 이면, f(n, m) = 1 + f(n, n-1)
이유는 당연합니다. 길이가 n 이하의 막대만 써서 길이가 n인 막대를 만드려면, n짜리 하나 써서 만들거나, n-1 이하인 막대들만 써서 만들면 됩니다. 둘은 절대 겹치지 않으니까요. 앞의 경우의 수는 1이고 뒤의 경우의 수는 정의에 의해 f(n, n-1)
1 < m < n 이면 f(n, m) = f(n, m-1) + f(n - m, m)
길이가 m 이하인 막대기만 써서 n짜리를 만들어야 합니다. 길이가 m인 막대기를 하나도 안쓰거나(그러면 남은 것들은 다 m-1 이하니까 n짜리를 m-1 이하로만 만드는 방법의 수 : f(n, m-1) ), 쓰면 됩니다. 쓰는 경우에는 길이가 n-m 인 막대기를, 적당히 길이가 m 이하인 막대기만 써서 만든 뒤, 거기다가 맨 뒤에 길이 m짜리 막대기를 대면 n짜리가 만들어지겠죠. 따라서 f(n-m, m) 입니다. 이 두 경우는 동시에 일어나는 것이 없으므로 f(n, m-1)과 f(n-m, m)을 더하면 됩니다.
14년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
MiNiST
안녕하세요.
이번에 저 문제가 과제로 나와서 생각해 보는데 식이 명쾌하게 이해가 되지 않아서 스팟분들의 도움을 청합니다.
f(n) = "n길이의 막대를 1~n-1 길이의 막대로 자르는 경우의 수" 라 하고 이것을 구하기 위해
f_sub(n,m) = n길이의 막대를 m이하의 막대를 사용하여 자르는 경우의 수로 하면
f(n) = f_sub(n-m, m) + f_sub(n, m-1)
이라는 점화식이 구해 진다고 합니다.
그런데 이 점화식이 잘 이해가 되지 않는데
명확하게 설명을 해주실수 있을까요?
14년 전