27737 버섯농장 [파이썬]

 

 

https://www.acmicpc.net/problem/27737

문제

농부 해강이는 𝑁×𝑁$N \times N$ 칸으로 이루어진 나무판에서 버섯 농사를 짓는다. 나무판은 버섯이 자랄 수 있는 칸과 없는 칸으로 이루어져 있다.

해강이는 𝑀$M$개의 버섯 포자를 가지고 있다. 버섯 포자는 버섯이 자랄 수 있는 칸에만 심을 수 있다.

각 버섯 포자는 포자가 심어진 칸을 포함해 최대 𝐾$K$개의 연결된 (버섯이 자랄 수 있는) 칸에 버섯을 자라게 한다. 이때 연결된 칸은 상하좌우로 적어도 한 변을 공유하는 칸들의 집합이라고 정의한다.

또한 한 칸에 버섯 포자를 여러 개 겹쳐서 심을 수 있으며, 만약 𝑥$x$개의 버섯 포자를 겹쳐 심으면 포자가 심어진 칸을 포함해 최대 𝑥×𝐾$x \times K$개의 연결된 (버섯이 자랄 수 있는) 칸에 버섯이 자란다.

 

<그림 1> 𝐾=4$K = 4$일 때 버섯이 자라는 모습이다.

 

<그림 2> 𝐾=10$K = 10$일 때 버섯이 자라는 모습이다.

해강이는 버섯 포자를 심을 때 최소 개수로만 심으려고 한다. 해강이가 농사가 가능할지 판단하고, 농사가 가능하다면 남은 버섯 포자의 개수를 출력하시오.

버섯 포자를 하나라도 사용하고 버섯이 자랄 수 있는 모든 칸에 버섯이 전부 자랐을 때 농사가 가능하다고 정의한다.

입력

첫 번째 줄에 𝑁$N$, 𝑀$M$, 𝐾$K$가 공백으로 구분되어 주어진다.

두 번째 줄부터 𝑁$N$개의 줄에 나무판의 각 칸의 상태가 공백으로 구분되어 주어진다.

버섯이 자랄 수 있는 칸은 0, 버섯이 자랄 수 없는 칸은 1로 주어진다.

출력

만약 버섯 농사가 불가능하면 IMPOSSIBLE을 출력한다.

버섯 농사가 가능하다면, POSSIBLE을 출력하고 다음 줄에 남은 버섯 포자의 개수를 출력한다.

제한

•  1≤𝑁≤100
•  0≤𝑀≤1000000
•  1≤𝐾≤10^8
•  N, M, K는 모두 정수이다.

서브태스크

번호배점제한

1	10	𝐾=1$K = 1$
2	90	추가적인 제약 조건이 없다.

 

 

문제풀이

 

0인 곳에 버섯을 심을 수 있다 심을 수 있는 구간을 구한 후 

심을 칸을 k로 나눈 후 나머지가 있는 경우 하나를 추가해서 심어준다

포자가 부족할 경우 IMPOSSIBLE

 

추가로 심을 구간이 없는 경우도 IMPOSSIBLE

해준다

 

 

코드