https://www.acmicpc.net/problem/11726
Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net1. 일단 점화식 끼워맞추기가 된다는걸 찾았고
2. 그러면 N-2에서 누운 타일 2개를 더한거
3. N-1 에서 세운 타일 1개를 더한거
4. 를 하면 N이 나온다는걸 그림판놀이로 알아냈는데
5. 이걸 증명은 어떻게함?
6. 약간 중복조합 섞는 느낌도 나는데, 이걸 이용해서 증명하는건 너무 직관적이진 않음
dp는 점화식 나온게 증명일텐데
그 점화식이 되는 이유에 대한 증명이 필요함
점화식 나왔다는게 일반항이 나왔다는거잖아. N에 대해 정리했으면 N-1, N -2, N -3.. 몇개 해봤을 때 성립하는걸 보이면 그게 점화식 증명이잖아 (식 세우고 저걸 해봐야, 구한 식이 점화식이라는걸 알 수 있으니. 점화식 나왔다는건 이미 저걸 해봤다는거 아냐??)
제가 원하는건, D[N] = DP[N-1] + DP[N-2] 임! 증명끝! 이게 아니라, DP[N] 은 이러이러한 원리에 의해서 DP[N-1] + DP[N-2] 이 됩니다 에서 이러이러한 원리에 대한 증명이 필요해요
본문에 썼다시피, 제가 말하는건 DP[N-2] 에서 누운 타일 2개를 더한 것들과 DP[N-1]에서는 세운 타일 1개를 더하면 이게 DP[N] 이 되는건데, 이 과정이 너무 그냥 얼렁뚱땅 나이브하다는겁니다 제가 자력으로 찾은거지만
https://namu.wiki/w/%EC%88%98%ED%95%99%EC%A0%81%20%EA%B7%80%EB%82%A9%EB%B2%95
그러니깐 식 구하고 저거 해서 나온게 점화식인데, 너가 말하는건 점화식을 구한 상태가 아니고 그냥 식 하나 나온 상태에서 그게 점화식임을 증명하는 방법이 궁금한거고, 그거 자체는 N에 대해서 성립함을 가정하고 N+1, N+2, N+3... 에 대해서 성립함을 보이면 그게 증명된거고 점화식 된거야
맨 마지막 줄에 하나 놓거나 두 줄에 두개 놓거나잖아 뭐가 증명이 필요함
그건 끼워맞추기잖아요
뭐가 그게 끼워맞추기야 그 방법밖에 없으니까 점화식이 그렇게 나오는건데
님은 완전탐색도 끼워맞추기라고 할꺼임?
좀 기다리면 개고수분이 오셔서 시원하게 답해줄듯..
아 이거 그냥 서로 말하는 핀트가 다른거같기도 하고
여기다 다시 써봄
DP[N], DP[N+1] 을 알고 있다 가정해봅시다
DP[N] 에서 누운타일 2개를 더한 것들 + DP[N+1] 에서 세운 타일 1개를 더한 것들이 왜 DP[N]인가?
아니 DP[N+2]
지금 상황
1. DP[N+2] 세보니깐 맞는데?
2. DP[N] 에서는 타일 2개 누은거랑 DP[N+1] 에서는 타일 세운거 1개 더하는거밖에 없는데? -> 왜 그거밖에 없는데?
내가 지금 필요한거
DP[N] 에서는 타일 2개 누은거랑 DP[N+1] 에서는 타일 세운거 1개 더하는거밖에 없음 -> 왜 그거 밖에 없음? 증명해보셈! -> 이거에 대한 증명
'DP[N], DP[N+1] 을 알고 있다 가정해봅시다' 가 아니고, 이것 저것 짜맞추다 보니깐 DP[N]에 대한 식을 구했어, 그 식이 맞나 알아보기 위해 N+1, N+2, N+3.... 넣어봐서 그 식 자체가 성립되나 확인하고, 성립하면 그때가 점화식이야
이거 맞음. 그럼 저 문제에서는 어떻게 dp식을 구했느냐 하면 그게 바로 아랫댓글. 점화식을 구하는 mechanical한 방법은 없는 거인
좋은 질문이라고 생각함. 일단 레퍼런스를 남기자면
https://doi.org/10.1007/BF02193034
너가 원하는 거에 대한 증명은 보통 profiling 이라고 부르는 방법론이 있고, 아쉽게도 왜 유효한 profile이 그것밖에 없냐는 건 보통 brute force임
이제 다른 방법은 전체 타일링을 더 작은 타일링 여러개로 쪼개는 방법임. 즉, 전체 타일링을 unbreakable 한 타일링으로만 구성할 수 있느냐는 건데. 이 문제에서 domino(1 x 2)만 사용하므로, brute force에 의해 2 x n unbreakable 타일링은 n=1, n=2 에서만 존재한다고 할 수 있음. 그러면 이제 길이 N의 타일링으로부터 N+1, N+2 타일링을 구성하는 방법이 결정됨
좀 더 오버킬하자면, domino covering에 관한 유명한 공식이 있음. 여기에 숫자 대입하면 얼추 수학적으로 보일 수는 있을 거임.
https://en.wikipedia.org/wiki/Domino_tiling
2 x n unbreakable 타일링은 n=1, n=2 에서만 존재한다고 할 수 있음. << 이거에 대한 설명 조금만더 가능할까요?
2 x 3 타일링을 예로 들자. 2 x 3 타일링이 unbreakable 하다면 2x1 타일링과 2x2 타일링을 모두 포함하지 않아야 함. 그런데 2 x 2 타일링을 벗어나려고 악을 쓰면 결국 2 x 3 타일링을 꽉 채울 수 없다는 결론이 나옴. 왜? unbreakable 하기 위해 윗줄 (or 아랫줄) 의 타일을 "한 칸 밀면" 그 한 칸을 채울 수가 없어서 타일링이 완성이 안 됨.
오 뭔가 이해될 것 같기도 하고 그러네여 좋은 댓글 감사합니다
2×n을 만드는 방법이 2x(n-1)에 세로블럭 1개 추가하는 방법 + 2×(n-2)에 가로블럭 2개 추가하는 경우 두개밖에 없으니깐
나머지 2×(n-3) 이하는 위 두 경우에 포함되고
2 x n을 채운다고 생각해보자. 오른쪽 위 칸을 채우는 방법은 세로 블럭 또는 가로 블럭임. 세로 블럭을 채운 경우에는 나머지를 채우는 가짓수가 2 x n-1을 채우는 가짓수와 같음 가로 블럭으로 채운 경우에는 오른쪽 아래 칸을 채우기 위해서 또 가로 블럭을 사용할 수밖에 없음. 그러면 나머지를 채우는 가짓수가 2 x n-2를 채우는 가짓수와 같음 그래서 n>=3인 경우에 dp[n]=dp[n-1]+dp[n-2]임.