plzrun   7년 전

점화식을 d[x][y] = d[x-2][y] + d[x-1][y-1] + d[x][y-2] 라고 세웠습니다.

(d[x][y]는 (x,y)까지 가는 모든 경우의 수)

이 점화식이 틀렸나요?...


맞는거 같은데 ㅠ? 어떵게 틀렸는지 모르겠어요

plzrun   7년 전

잘못됐다는군요.. ㅠ

f52985   7년 전

3 5

정답 : 6

출력 : 7


d[3][3]=4

d[2][4]=2

d[1][5]=1

인것은 맞지만,


d[3][3]으로 가는 4가지 경로를 살펴보면 아래서 들어오는 2가지, 왼쪽에서 2칸 전에 들어오는 1가지, 그리고 왼쪽에서 1칸전에 들어오는 1가지가 있습니다.

따라서 이를 고려하지 않고 d[3][5]에 그냥 더해줄 경우, 왼쪽에서 1칸 전에 들어와서 바로 위로 올라가는 불가능한 경우까지 계산됩니다.

plzrun   7년 전

해결했습니다. 회전방향 4개를 디피식에 더 추가해서 해결했어요. ㅎ

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