티스토리 뷰

반응형


백준 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



반응형

'알고리즘 문제 > DP' 카테고리의 다른 글

백준 1463 1로 만들기  (0) 2019.09.17
백준 15483 최소편집  (0) 2018.12.30
백준1126 같은탑  (0) 2017.12.05
BOJ 1520 : 내리막길  (0) 2017.11.11
백준 9095 : 1, 2, 3 더하기  (0) 2017.10.10