FindBox

Author

anri

2000

Imagine a box which is full of coins. You want to get it, but you don't want other people to see that you're going towards it, so you're going to go backwards.

Assume that the box is located at (0, 0), and you are located at (x, y). You can move only backwards and leftwards to reach the box, and your step is 2 points long (it's just the way your legs work).

Calculate how many paths you can take to reach the box, or return "0" if you can't reach it.

Example

For x = 4 and y = 4, the output should be
findBox(x, y) = "6".

Here's the number of paths you can take to reach each of the points from (0, 0) to (4, 4):

 y
 ^
 | 1, 0, 1, 0, 1
 | 0, 0, 0, 0, 0
 | 3, 0, 2, 0, 1
 | 0, 0, 0, 0, 0
 | 6, 0, 3, 0, 1
 0--------------> x

• [input] integer x

  The x coordinate of your position, 1 ≤ x ≤ 50.

• [input] integer y

  Th y coordinate of your position, 1 ≤ y ≤ 50.

• [output] string

  The number of paths you can take.

먼저 출발지에서 목적지까지의 거리를 담은 2차원 배열을 선언한다.

test case에 엄청나게 큰 예제가 있으므로 배열은 long long으로 선언..

그 후 2차원 배열을 탐색하면서, Dynamic Programming 을 이용.

고딩때 최단거리 문제 풀 때 자주쓰던 방법이랑 비슷하게 작성하면 된다.

해당 위치의 바로 밑, 그리고 바로 왼쪽의 거리를 더하면 해당 위치까지 가는 최단거리가 되는 것을 이용한다.

풀긴 풀었다.

문제는 좀 심각하게 길다.

평균적으로 100~150자 이내로 완료하는데 무려 244자...

다른 사람들은 어떻게 풀었을까?

참조

- https://www.quora.com/How-do-you-count-all-the-paths-from-the-first-element-to-the-last-element-in-a-2d-array-knowing-you-can-only-move-right-or-down     [Dynamic Programming]