14890번. 경사로

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

 

 

 

https://yabmoons.tistory.com/49

해설은 이 블로그를 참고했다. 

별다른 알고리즘이 사용되지 않지만, 쉽지는 않은 문제이다.

경계값 등 변수값을 정해줄 때 사람 헷갈리게 하는 점이 많기 때문이다...

 

파이썬으로 이 문제를 풀 때 유의해야 하는 점은 파이썬의 for문은 다른 언어와 다르다는 점이다.

c에서는 for (int i=0; i<n; i++) 하고 for문 내에서 i를 증가시킬 수 있지만,

python에서의 for i in range(n)은 for문 내에서 i 값을 변경시켜도 다음 반복 시 원래 값으로 돌아온다는 것.

 

이 문제에 적용해보면 다음과 같다. 여기서 한 번 경사로를 지은 곳은 다시 살필 필요가 없다. 쩜프쩜프! 

예를 들어 어떤 행이 [ 3 2 2 1 ]이고 경사로 길이가 2였을 때, 첫 번째 주인공은 3이다.

자, 그러면 2 2 위에 경사로가 지어질 것이고.

그 다음 반복문의 주인공이 되야 하는 것은 첫번째 2를 건너뛰고 바로 두 번째 2 가 된다.

왜냐하면 한 곳 위에 두 개의 경사로가 지어질 수 없다고 문제에 나와있기 때문이다.

(*주의: 바로 1로 가면 안 된다. 이게 이 문제의 헷갈리는 점인데...두번째 2 다음에 1이 나오므로 여기에도 경사로를 지어줘야 하기 때문이다!)

아무튼 그래서 반복문 내에서 다음 주인공 원소를 만들기 위해 점프 점프 할 필요가 있고, 그래서 while문을 썼다.

 

결론.

이 시뮬레이션 문제는, 

첫째는 평평한 땅을 지날 때 카운트를 증가시켜준다는 것,

두번째는 경계값이나 각종 값 정해줄 때 신경써야 하는 것

이게 핵심인거같다.

 

import sys


def make_road(board):
    total_road = 0
    for col in range(n):
        can_be_road = True
        flat_num = 1

        row = 0
        while row < n-1:  # 반복문 내에서 row 값을 변경시킬 것이므로 for 대신 while을 쓴다.
            if board[row][col] == board[row+1][col]:  # 같은 값을 유지할 때
                flat_num += 1
                row += 1
            elif board[row][col] + 1 == board[row+1][col]:  # 높은 길을 만났을 때
                if flat_num >= l:  # 경사로 지을 수 있음
                    flat_num = 1  # 초기화
                    row += 1
                else:
                    can_be_road = False # 경사로를 한번 놓을 수 없으면 그 길은 끝
                    break
            elif board[row][col] - 1 == board[row+1][col]:  # 낮은 길을 만났을 때
                standard = board[row+1][col]
                for i in range(l):
                    if row+1+i >= n or standard != board[row+1+i][col]:  # 경사로 범위를 넘어서거나 차이가 1 이상일 때
                        can_be_road = False
                        break
                if can_be_road:
                    flat_num = 0
                    row += l
                else:
                    break
            else:
                can_be_road = False
                break
        if can_be_road:
            total_road += 1

    return total_road


if __name__ == '__main__':
    n, l = map(int, sys.stdin.readline().split())
    board_origin = []
    for _ in range(n):
        board_origin.append(list(map(int, sys.stdin.readline().split())))

    board2_origin = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            board2_origin[i][j] = board_origin[j][i]
    # 세로 길
    print(make_road(board_origin)+make_road(board2_origin))