백준 15991 1, 2, 3 더하기 - 6

백준 15991 1, 2, 3 더하기 - 6

문제 보러가기 

https://www.acmicpc.net/problem/15991

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 합은 대칭을 이루어야 한다.

1+1+1+1

1+2+1

2+2

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

경우의 수 문제이다. 이 문제를 푸는데 무려 2달 이나 걸렸다. 2달 전 처음 접했을 때 엄청 푸려고 노력했다. 한 4일 정도 노력을 했는데 안풀렸다. 특수한 스킬이 필요한 것이 아니라 이해력 문제였는데 못 풀었기 때문에, 그리고 또 이 문제 시리즈를 1, 2, 3, 4, 5, ... 순서대로 풀려고 했는데 6에서 막혔던 점이 좀 안 좋은 기억으로 남아있고 풀려고 할때면 항상 잠이 들었다. 그러다 우연히 ...  일기는 그만 ...

나는 문제가 이해가 안가 질문 글을 남겼었다.

https://www.acmicpc.net/board/view/27902

일단 위 글에 정답은 적혀있다.

내 나름대로 정리하자면, 대칭적인 타일을 만들기 위해, 다음과 같은 방법이 제시된다.

아, 우선 이 문제를 풀기위해선 경우의 수와 그 덧셈, 그리고 경우의 수 dp 구현에 대해 알고 있어야하며, 그냥 애초에 이전 시리즈 1,2, 3, 4.... 등을 풀 수 있어야한다.

그래서 일단 대칭적인 타일을 만들기 위해선, 다음을 상상해보자.

모든 일반적인 1, 2, 3 더하기 경우의 수는 다음과 같이 정의하자.

1 : {1 }, 2 : {1+1, 2}, 3 : {1+1+1, 1+2, 2+1, 3 } , 4 : {1+ 1+ 1+ 1 , 1+2 +1, 2+1 +1, 1+1+2, 3+1, 1+3, .... } 생략.

일단 내 주머니 안에 모든 일반적인 1,2, 3 더하기 경우의 수 들을 무한히 가지고 있다고 하자. 

이 때, 만약 i 길이 만큼의 대칭 수열을 만들려고 할 때 다음을 따르면 된다.

1 만약 만들려는 대칭 수열 길이 i가 짝수이면 나는 다음과 같이하면 된다.

-> 주머니 안에서  i/2 인 수열을 동일한 것을 두 개 꺼내 이어 붙인다. 또는 (i-2)/2 인 수열을 동일한 것을 두 개 꺼내 2 를 사이에 두고 이어 붙인다. 

2 만약 만들려는 대칭 수열 길이 i가 홀수이면 나는 다음과 같이 하면된다.

-> 주머니 안에서 (i-1)/2 인 수열을 동일한 것을 두 개 꺼내 1을 사이에 두고 이어 붙인다. 또는 (i-3)/2 인 수열을 동일한 것을 두개 꺼내 3을 사이에 두고 이어 붙인다.

이것으로 대칭 수열을 만드는 것을 완료 할 수 있다. 다만, 초기의 1, 2, 3 블럭은 그 자체로 대칭이기 때문에 어떻게 처리해줘야하나 고민이 되었다. 이 때는 d[0]=1을 이용했다. 0을 양옆에 놔두는 것 그 자체만으로도 대칭이 된다고 가정을 해준다고 일반화 했다.

https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/15991.cc