[백준 14890] 경사로

문제 보기

이 문제는 시뮬레이션 문제이다.

문제를 풀다보니 코드가 점점 더러워지는 느낌이다..

문제에서 주어지는 조건은 다음과 같다.

이 조건들을 잘 따지면 정답을 구할 수 있다. (말은 쉽지만 이 문제 푸는데 아주 오래 걸렸다...)

이 문제를 푸는데 사용한 로직은 다음과 같다.

1. 같은 높이의 블럭이 나오면 갯수를 센다. (13~14번째 줄)

2. 다음 블럭의 높이가 2 이상 차이나면 조건을 위반하므로 flag를 False로 바꾼다. (29~31번째 줄)

3-1. 다음 블럭이 높을때, count와 경사로의 길이를 비교한다. count가 더 작으면 경사로를 놓을 수 없다는 의미이고, count가 경사로의 길이보다 같거나 더 크면 경사로를 놓을 수 있다는 의미이다. 그러므로 경사로를 놓고 count를 1로 초기화 시켜준다. (16~22번째 줄)

3-2. 다음 블럭이 낮을때, count를 0보다 같거나 큰 지 비교하고, 만약 그렇다면 경사로를 놓을 수 있다는 의미이므로 count를 -(경사로의 길이 - 1)로 설정한다. 아니면 앞에서 경사로를 놓는 도중 또 다른 낮은 블럭을 만났다는 의미이므로 경사로를 세울 수 없다. (23~28번째 줄)

4. 마지막으로, 만약 내려가는 경사로를 짓는 도중 길이 끝이 난다면, flag는 True이지만 count는 음수인 상태가 된다. 이를 확인해준다. (33~34번째 줄)

1~3번에 해당하는 로직들은 다음 그림을 통해 이해할 수 있다.

4번에 해당하는 로직의 예는 다음 그림을 통해 이해할 수 있다.

n, l = map(int, input().split())
board = [list(map(int, input().split())) for c in range(n)]
board2 = list(list(r) for r in zip(*board))
    
answer = 0
for i in range(n):
    
    # horizontal traverse
    j, count = 0, 1
    flag = True
    while j + 1 < n:
        diff = abs(board[i][j] - board[i][j + 1])
        if diff == 0:
            count += 1
        elif diff == 1:
            # uphill
            if board[i][j] < board[i][j + 1]:
                # condition 4. it's too short to place a slope way
                if count < l:
                    flag = False
                else:
                    count = 1
            # downhill
            else:
                if count >= 0:
                    count = -l + 1
                else:
                    flag = False
        # condition 2. the difference is greater than 1
        else:
            flag = False
        j += 1
    if count >= 0 and flag:
        answer += 1
    
    # vertical traverse
    j, count = 0, 1
    flag = True
    while j + 1 < n:
        diff = abs(board2[i][j] - board2[i][j + 1])
        if diff == 0:
            count += 1
        elif diff == 1:
            # uphill
            if board2[i][j] < board2[i][j + 1]:
                # condition 4. it's too short to place a slope way
                if count < l:
                    flag = False
                else:
                    count = 1
            # downhill
            else:
                if count >= 0:
                    count = -l + 1
                else:
                    flag = False
        # condition 2. the difference is greater than 1
        else:
            flag = False
        j += 1
    if count >= 0 and flag:
        answer += 1
print(answer)