gaelim   5년 전

음.... 이틀간 고민을 했는데도, 뚜렷한 경우의 수 생성방법을 찾지못했습니다.

접근 하는 방법에서 조언이 필요합니다... 

jh05013   5년 전

조합이 대칭이므로 반쪽만 있으면 조합 양쪽을 모두 표현할 수 있습니다.

gaelim   5년 전

@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 로 점화식을 세워봤는데 여전히 .. 뭔가 모지란느낌입니다.. 

풀릴듯 말듯하여 질문 남깁니다. 아래에 소스남겼습니다.

gaelim   5년 전

위소스는 반례케이스는 바로 눈에 보이긴하지만, 제 상태가 어떤지를 보여드리려고 남깁니다. 감사합니다.

jh05013   5년 전

" d[i]에는 그 자체로 대칭이 있는 것이 있기때문에 쓸 수 없다"가 무슨 뜻인지 잘 모르겠습니다. 4 = 1+1+1+1도 올바른 조합입니다.

답이 n/2+1로 계산되고 있는 것 같은데, 정답에 비해 상당히 작습니다.

힌트를 드리자면, 예상하셨듯이 먼저 조합을 네 가지 종류로 나눌 수 있습니다.

  1. 길이가 짝수이며, 반쪽의 합이 특정 값과 같음
  2. 길이가 홀수이며, 중심에 1이 있고, 중심을 제외한 반쪽의 합이 특정 값과 같음
  3. 중심에 2가 있고, ...
  4. 중심에 3이 있고, ...

이제 "합이 특정 값이 되는 반쪽의 가지수"를 구하는 과정은 어디선가 익숙한 문제로 귀결될 것입니다.


gaelim   5년 전

감사합니다. 조금 오래걸렸지만, 말씀하신 방법으로 해결했습니다. 

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