nisroeld99   4년 전

안녕하세요 풀다가 도저히 안되서 질문올립니다.



재귀로 풀었고


경우가

1. 새로시작하거나

2. 왼쪽에 붙이거나

3. 위쪽에 붙이거나


3가지 박에없고 ,  

for (i=0; i<n; i++)

  for(j=0;j<m;j++){

  }

순서이므로, 왼쪽 위로는 다 채워져있다고 가정했습니다. 


근데 3,4 까지도 되는데, 


4,4부터는 경우의수가 기하급수적으로 많아지는 것 같습니다.


혹시 제가 접근한게 잘못한건지 아니면  가지를 치는 트릭이 있는지 궁금합니다.



답변 부탁드립니다. 감사합니다 

zlzmsrhak   4년 전

이 문제는 동적계획법으로 해결할 수 있습니다. 백트래킹으로도 풀 수 있을 것 같지만, 함수 호출 한 번당 수행하는 연산 수가 매우 적어야 될 것 같습니다.

nisroeld99   4년 전

dp는 어떻게 할까요 


백트레킹은 성공했습니다!

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