반응형 미노1 백준 #1648 격자판 채우기(동적 계획법) 이번 문제는 플래티넘으로 등급이 매겨진 문제입니다. 격자판의 크기가 주어지면, 2x1 미노로 격자판을 채우는 것입니다. 빈 곳이 있으면 안되고, 꽉 채우는 경우의 수를 계산하는 프로그램입니다. 일견 어려워보일 수 있겠지만, 동적 계획법을 잘 사용하면 쉽게 풀 수 있습니다. 2x1 미노를 세로 또는 가로로 채우는 문제이기 때문에 한줄을 다 채웠을 경우 다음줄에는 말끔하지 않게 되어 있을 수가 있습니다. 예를 들어서 3x6 격자판을 채운다고 해보죠. 첫줄을 채우는 방법은 다음의 두가지입니다. 두번째 줄의 모양에 따라서 안 채워진 곳은 0, 채워진 곳은 1이라고 한다면, 위의 두 패턴은 001과 100이 됩니다. 초기 패턴은 000이라고 할 수 있습니다. 그러면 우리는 점화식으로 다음과 같이 놓을 수 있습니다.. 2022. 9. 21. 이전 1 다음 728x90
