다이나믹프로그래밍 2

다이나믹 프로그래밍3

#11727 또 다시 타일링 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 이번 문제의 점화식은 내 힘으로 찾았다. (노가다) 팁? 이라 하면, An 을 An-1과 An-2등 이 전의 값으로 조합하여 찾는게 팁이 될 수 있을지도 모르겠다. 그렇게 제출 했는데 또 자꾸 틀려서 많이 화가 났다. 자꾸 출력 형식을 무시하고 제출해서 그런거였다. 그렇게 세 번을 틀렸다. 병X.... 어제도 그러더니... 실수가 반복되면 실력이랬다. 엥 근데 또 틀렸다 (100%에서) 뭐지?.....

다이나믹 프로그래밍2

내가 생각하는 다이나믹 프로그래밍의 핵심은 점화식을 파악하는데 있다. 그러니까 고등학교 때 봤던 확률과 통계 느낌 나는 문제들을 이해하는게 아주 중요하다. #11726번 2xn 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net n의 변화에 따른 타일링의 경우의 수를 계산해주면 되는데 내가 처음 판단한 점화식은 이렇다. An = An-1 + (n-2) 였다. 뭐 예상한 결과다. 고민고민 하다가 결국엔 서치... 결론은 An = An-1 + An-2 였고 맞추긴 ..

728x90