1388번: 바닥 장식

Difficulty : Silver IV

Problem Description

There is a floor sized N * M. You have to fill this floor with vertical and horizontal wooden plank.

The input is 'N' and 'M' for the first line, and the design of the floor in the other line.

If the part of the design is connected by one line, it can be made from a single wooden plank.

Here is an example. When the input is '-------', only one plank whose length is 7 is needed.

Now, the output is the least planks to make the design.

 

Solution

I counted the planks that are not connected with top and left plank. If they are connected, I didn't count.

 

'N' and 'M' is the size of floor.

b is the design of the floor, and c is for count.

 

For every parts of floor, if the part is not connected with top and left part, count it.

Don't forget to consider the case that 'i' or 'j' is out of size.

 

 

 

Today's English

plank : 판자

 

여담

골드 문제를 푼 사람이 많은 것부터 차례대로 해보려고 했는데 그래프가 앞부분에 도배되어 있었다.

그래프를 아예 못해서 공부해보려고 한글로 된 그래프 문제 중 가장 쉬운 것을 골랐는데 막상 풀고 나니 그래프를 사용할 필요가 없는 문제였다. 그래프에 익숙해질 때까지 당분간은 실버 난이도의 그래프 문제를 풀 예정이다.