waylight3   1년 전

(11111)

| |

(1111) (111)

| | | |

(111) (11) (11) (1)

| |

(11) (1)


11111의 경우 이런식으로 계속해서 내려갑니다.

그러다보면 맨 마지막에는 다 0이 되면서 끝나겠지요.

이때 0의 개수 (최하단의 노드 수)를 세면 그것이 문제에서 요구하는 경우의 수와 일치할 것입니다.

제가 그린 그래프에서 보면 (11111)이 (111)로 바뀌는 과정은 맨 끝 카드를 11로 결정하는 과정과 같으며

이어서 (111)이 (1)로 변하는 것은 결국 1, 11, 11 이렇게 분할하는 것을 나타내는 것이니

결국 0이 되며 분할이 끝나면 하나의 케이스를 찾은 것이죠!


이러면 77777처럼 무조건 1가지 경우밖에 없는 케이스도 잘 돌아가고, 11111처럼 케이스가 꽤나 다양한 경우도 돌아가는데

틀렸다고 나오는 걸 보니... 제가 뭘 잘못 생각하고 있는 건가요? 빠뜨린 경우의 수는 없는 것 같은데...


원래 목표는 이렇게 재귀로 짠 다음 DP로 만들어서 풀려고 했는데 ㅠㅠ

koosaga   1년 전

맞는 논리인거 같지만 숫자가 너무 큽니다. int형은 대략 9자리만 저장할 수 ㅇ

koosaga   1년 전

ㅣㅆ어요.

waylight3   1년 전

long long으로 바꾸었는데, 그래도 너무 작은가요?? 계속 틀리네 ㅠㅠ

koosaga   1년 전

넵 long long은 18자리 정도가 한계에요. 그리고 그 부분을 해결해도 시간 복잡도가 2^N이라..

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