5569번 - 출근 경로
점화식을 d[x][y] = d[x-2][y] + d[x-1][y-1] + d[x][y-2] 라고 세웠습니다.
(d[x][y]는 (x,y)까지 가는 모든 경우의 수)
이 점화식이 틀렸나요?...
맞는거 같은데 ㅠ? 어떵게 틀렸는지 모르겠어요
잘못됐다는군요.. ㅠ
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칸 전에 들어와서 바로 위로 올라가는 불가능한 경우까지 계산됩니다.
해결했습니다. 회전방향 4개를 디피식에 더 추가해서 해결했어요. ㅎ
댓글을 작성하려면 로그인해야 합니다.
plzrun 7년 전
점화식을 d[x][y] = d[x-2][y] + d[x-1][y-1] + d[x][y-2] 라고 세웠습니다.
(d[x][y]는 (x,y)까지 가는 모든 경우의 수)
이 점화식이 틀렸나요?...
맞는거 같은데 ㅠ? 어떵게 틀렸는지 모르겠어요