1577번: 도로의 개수

Difficulty : Gold V

Problem Description

There is a city. It is N * M size and grid shape.

And there are several roads under construction.

You have to calculate the number of all shortest paths from (0, 0) to (N, M) except constructing roads.

 

Solution

The algorithm to calculate the problem is the number to reach (A, B) is the sum of the number of (A-1, B) and (A, B-1).

 

Like this

N, M are the size of the city.

K is the number of constructing roads.

Arr is for the constructing roads.

Dict is numbers of ways from (0, 0) to (a, b).

 

Store the coordinate of constructing roads in arr.

And set the initial value.

 

8~9 : i for the row number, and j for the column number.

10 : if (0, 0), the value is already setted to 1.

11~14 : Set values of the first row and the first column.

15~16 : (a, b) = (a-1, b) + (a, b-1)

17~20 : If the road is in arr, cancel the count of that way.

 

Today's English

constructing : 공사중인

coordinate : 좌표

 

여담

DP는 재귀함수를 기반으로 하는 알고리즘이라고 생각해서 아무 생각 없이

재귀함수로 풀었다가 시간초과로 틀렸다.

재귀함수는 주어진 값이 작은 경우가 아니라면 자제하는 것이 좋겠다.