2591_숫자카드

정말 dp로 문제를 풀어나가는데 어려움을 느낀다.

시험이 끝나고 dp문제를 많이 풀어봐야겠다. dp를 잘 풀어야 문제해결능력이 높다고 할 수 있다는 것을 깨달았다. 

이 문제는 dp에 대한 풀이경험이 많다면 충분히 풀 수 있는 문제였다.

우선 문제에 대해서 정리하자면

1~34까지의 숫자가 적힌 카드가 있다. 

어느 한 숫자들 문제에서 보면 27123을 이 숫자카드를 나열하여 만들 수 있는 경우의 수를 구하는 문제였다. 

처음에는 dp인지도 모르고 백트래킹으로 풀어냈다. 

처음에 2인 카드를 놓는 경우에 그 다음 카드부터 7 또는 27카드를 놓을 수 있는 경우의 수와 함께

분기시켜며 결국 답을 구해냈다. 하지만 시간초과 ㅜㅜ 

이 문제는 찾아보니 dp문제였다. 

1~40자리의 수 이므로 백트레킹으로는 아무리 줄이더라도 정말 어마어마한 숫자가 나온다. 

그래도 1자리와 2자리 조건이 있으므로 충분히 시간 안에 답이 나올 수 있을 것이라 생각했는데 

아니었다. 

그 이후로는 도저히 방법이 생각 안나 막혔는데, 도움을 얻고 풀어냈다 생각의 전환이 필요했다. 

27123을 나열할 때 

2 -> 27 , 1 -> 12 -> 123 이 피보나치 수열의 형태로 경우의 수를 가진다는 것을 알았다. 

0으로 끊키거나, 2자리수가 34가 넘는 수는 피보나치의 형태를 깨뜨리고 다시 시작하게 되었다. 

예전에 풀었던 자리배치 dp문제와 완벽히 비슷한 문제였는데, 풀어내지 못 해서 아쉽다. 

자리배치 문제는 고정석을 경계로 피보나치의 값을 가지는데 이 경우는 10, 20, 30과 34를 넘는 수에서 피보나치가 끊키고

약간의 조건만 걸어주면 되는 문제였다. 

경우의 수 문제에서는 시간 안에 풀 수 없다면 피보나치를 한 번 생각해보자!!