경사로 [백준 14890번]

문제

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

14890번: 경사로

 

내 풀이

[3, 2, 1, 1, 1,]처럼 생긴 도로가 있다고 해보자.

이 도로를 [[3], [2], [1, 1, 1]]와 같이 생긴 temp로 만들었다.

 

temp를 돌면서 temp[i-1]과 temp[i] 안의 숫자가 몇 차이 나는지 확인하였다.

1 차이가 나면 check를 사용하여 방문 체크를 해주었다. 방문 체크를 하는 이유는 경사로가 이미 있는 곳에 또 경사로를 놓지 않게 하기 위함이다.

check[i] < len(temp[i])는 temp[i]에 경사로를 놓을 자리가 남아 있음을 뜻한다.

 

여기서 중요한 것은 check이다.

도로가 [3, 2, 1, 1, 2, 3]이고 L=1인 경우, 첫 번째와 두 번째 1 모두에 경사로를 놓을 수 있다.

그래서 temp[i]에 길이가 L인 경사로를 놓았으면, check[i]에 L을 더해주었고, 다음 경사로를 놓기 전에 check[i]에 칸이 얼마나 남았는지 확인하여 칸이 남아있다면 check[i]에 경사로를 놓을 수 있도록 하였다. len(temp[i]) - check[i] >= L

 

행과 열을 모두 체크하여야 한다.

행만 계산하는 것을 구현하고, 열을 구할 때에는 행열을 전치시켰다.

N, L = map(int, input().strip().split())
grid = [list(map(int, input().strip().split())) for _ in range(N)]

def can_go(grid):
    cnt = 0
    for load in grid:
        temp = [[load[0]]]
        for i in range(1, len(load)):
            if load[i] == temp[-1][-1]:
                temp[-1].append(load[i])
            else:
                temp.append([load[i]])
        flag = True
        if len(temp) == 1:
            flag = True
        else:
            check = [0]*len(temp)
            first = temp[0][0]
            for i in range(1, len(temp)):
                if abs(first - temp[i][0]) == 1:
                    if first < temp[i][0] and len(temp[i - 1]) - check[i-1] >= L and check[i-1] < len(temp[i-1]):
                        check[i-1] += L
                        first = temp[i][0]
                    elif first > temp[i][0] and len(temp[i]) - check[i] >= L and check[i] < len(temp[i-1]):
                        check[i] += L
                        first = temp[i][0]
                    else:
                        flag = False
                        break
                else:
                    flag = False
                    break
        if flag:
            cnt += 1
    return cnt
print(can_go(grid) + can_go(list(map(list, zip(*grid)))))

 

총평

시뮬레이션은 꼼꼼함이 핵심이다.

별다른 알고리즘 필요없다.

여기서는 꼼꼼함이 곧 알고리즘이다.