조합이 대칭이므로 반쪽만 있으면 조합 양쪽을 모두 표현할 수 있습니다.
15991번 - 1, 2, 3 더하기 6
@jh05013 님 답변감사합니다.
제가 접근을 할 떄 그 방법을 생각했으나, 잡힐듯 말듯하여 좀 더 전진 하지 못 했습니다.
어제부터 계속해서,, 저는 다음과 같이 생각을 조금씩 전진해보았습니다.
어떤것이 부족한지 짚어주셨으면 좋겠습니다.
일단은 기본적인 모든 경우의 수를 다 구하면, d vector 에 저장해 놓아서, 말씀하신대로 그 자체를 대칭시키면 (그게 반쪽이기때문에) 반드시 대칭성이 있다고 생각합니다.
그래서 제가 a vector 를 만든뒤, ai 는 대칭성이 있는 임의의 수열 i길이를 뜻함, a[i] = d[i/2]
라고하고, input 이 n이면 a[n] 을 출력하면 되겠다고 생각했었는데 d[i]에는 그 자체로 대칭이 있는 것이 있기때문에 (예, 1+1) 이 방법으로는 이걸 쓸 수 없겠더라구요.
그래서 그냥 제가 가지고 있는 블럭 {1, 2, 3} 을 끼어넣을 수 있는 둘로 딱 나눠 지는 어떤 것을 d vector 로 점화식을 세워봤는데 여전히 .. 뭔가 모지란느낌입니다..
풀릴듯 말듯하여 질문 남깁니다. 아래에 소스남겼습니다.
" d[i]에는 그 자체로 대칭이 있는 것이 있기때문에 쓸 수 없다"가 무슨 뜻인지 잘 모르겠습니다. 4 = 1+1+1+1도 올바른 조합입니다.
답이 n/2+1로 계산되고 있는 것 같은데, 정답에 비해 상당히 작습니다.
힌트를 드리자면, 예상하셨듯이 먼저 조합을 네 가지 종류로 나눌 수 있습니다.
이제 "합이 특정 값이 되는 반쪽의 가지수"를 구하는 과정은 어디선가 익숙한 문제로 귀결될 것입니다.
댓글을 작성하려면 로그인해야 합니다.
gaelim 5년 전
음.... 이틀간 고민을 했는데도, 뚜렷한 경우의 수 생성방법을 찾지못했습니다.
접근 하는 방법에서 조언이 필요합니다...