[백준][파이썬] 14890번 : 경사로(코드, 해설, 풀이)

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

14890번: 경사로

 

---

- 문제

  경사로의 길이가 L인 만큼 L이 3이라면 3 2 2 2와 같은 식으로 3보다 1작지만 3의 길이를 수용할 수 있는 2 2 2가 3개 있는 곳에만 경사로를 설치할 수가 있다. 경사로가 설치되면 해당 부분은 높이가 일정하다고 생각하면 된다. 이제 가로, 혹은 세로로 높이가 같아서 사람이 지나다닐 수 있는 길이 총 몇개가 되는지를 맞추는 문제이다.

 

  사람이 지나다닐 수 있는 길이 되기 위해서는 가로 혹은 세로의 한 줄의 높이가 모두 같아야 한다.

 

---

- 해설

 

  모든 길이 사람이 지날 수 있는 길이라고 가정하고 조건에 부합하는 경우 길이 될 수 없다는 식으로 하나씩 바꿔나가는 방식으로 문제를 풀 수 있을 것 같다. 이때 고려해야 하는 조건으로는 

 

1. 높이가 모두 같은 경우

: 이때는 길이 될 수 있으므로 생략한다.

 

2. 높이가 차이나는 경우

: 이때는 높이의 차이에 따라 달라지는데, 1만 차이나는 경우에는 경사로의 길이 L이랑 지금까지 높이가 일정했던 길이를 구한 다음에 비교하도록 한다. 하지만 1보다 더 많이 차이나는 경우에는 그만큼 경사로를 더 설치해야 하므로 차이나는 만큼의 경사로를 구하고 그만큼 경사로를 설치할 수 있는지 비교해야 한다.

 

---

- 풀이

import sys

N,L = map(int,sys.stdin.readline().split())
maze = [[0]*N]*N
boolmaze1 = [True]*N
boolmaze2 = [True]*N
for i in range(N):
    temp = list(map(int,sys.stdin.readline().split()))
    maze[i] = temp
for i in range(N):
    compare = maze[i][0]
    cnt_same = 1
    for j in range(1,N):
        if compare == maze[i][j]:
            cnt_same += 1
        elif compare != maze[i][j]:
            if cnt_same < 0:
                boolmaze1[i] = False
                break
            elif compare == maze[i][j] + 1:
                cnt_same = 1 - L
            elif compare + 1 == maze[i][j]:
                if cnt_same < L:
                    boolmaze1[i] = False
                    break
                else:
                    cnt_same = 1
            else:
                boolmaze1[i] = False
                break
        if cnt_same < 0 and j == N-1:
            boolmaze1[i] = False
        compare = maze[i][j]

    compare = maze[0][i]
    cnt_same = 1
    for j in range(1,N):
        if compare == maze[j][i]:
            cnt_same += 1
        elif compare != maze[j][i]:
            if cnt_same < 0:
                boolmaze2[i] = False
                break
            elif compare == maze[j][i] + 1:
                cnt_same = 1 - L
            elif compare + 1 == maze[j][i]:
                if cnt_same < L:
                    boolmaze2[i] = False
                    break
                else:
                    cnt_same = 1
            else:
                boolmaze2[i] = False
                break
        if cnt_same < 0 and j == N-1:
            boolmaze2[i] = False
        compare = maze[j][i]
a = boolmaze1.count(True)
b = boolmaze2.count(True)
print(a+b)

  나는 모든 가로와 세로의 길이 사람이 지나다닐 수 있는 길이라고 가정을 한 상태에서 길의 조건에 부합하지 않는 경우를 하나씩 빼는 방식으로 코드를 작성했다. 가로/세로의 첫번째 index와 비교하여 그 다음 index의 높이가 같은 개수를 구하고 높이가 달라지면 L이랑 비교해서 경사로를 설치할 수 있는지 찾았다. 이때 경사로를 설치할 수 없다면 해당 길은 사람이 다닐 수 없는 길이 되고, 경사로를 설치할 수 있으면 변하는게 없다.

 

  이걸 세로와 가로 두 방향으로 진행하여 마지막에 사람이 다닐 수 있는 길인지 boolean 형식으로 만들어놓은 boolmaze를 .count(True)를 해서 개수를 찾았다.