14391번 - 종이 조각
안녕하세요 풀다가 도저히 안되서 질문올립니다.
재귀로 풀었고
경우가
1. 새로시작하거나
2. 왼쪽에 붙이거나
3. 위쪽에 붙이거나
3가지 박에없고 ,
for (i=0; i<n; i++)
for(j=0;j<m;j++){
}
순서이므로, 왼쪽 위로는 다 채워져있다고 가정했습니다.
근데 3,4 까지도 되는데,
4,4부터는 경우의수가 기하급수적으로 많아지는 것 같습니다.
혹시 제가 접근한게 잘못한건지 아니면 가지를 치는 트릭이 있는지 궁금합니다.
답변 부탁드립니다. 감사합니다
이 문제는 동적계획법으로 해결할 수 있습니다. 백트래킹으로도 풀 수 있을 것 같지만, 함수 호출 한 번당 수행하는 연산 수가 매우 적어야 될 것 같습니다.
dp는 어떻게 할까요
백트레킹은 성공했습니다!
댓글을 작성하려면 로그인해야 합니다.
nisroeld99 6년 전
안녕하세요 풀다가 도저히 안되서 질문올립니다.
재귀로 풀었고
경우가
1. 새로시작하거나
2. 왼쪽에 붙이거나
3. 위쪽에 붙이거나
3가지 박에없고 ,
for (i=0; i<n; i++)
for(j=0;j<m;j++){
}
순서이므로, 왼쪽 위로는 다 채워져있다고 가정했습니다.
근데 3,4 까지도 되는데,
4,4부터는 경우의수가 기하급수적으로 많아지는 것 같습니다.
혹시 제가 접근한게 잘못한건지 아니면 가지를 치는 트릭이 있는지 궁금합니다.
답변 부탁드립니다. 감사합니다