[백준] 14890:경사로

백준의 14890: 경사로

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

14890번: 경사로

문제풀이 과정

1. 각각의 행과 열을 한 개씩 list형태로 함수에 집어넣는다.

2. 모든경우의 수를 생각해서 가지치기해준다.

처음 문제 풀 때는 어떤 자료구조 개념이 필요한지 고민했다.

약 1시간 정도 헤매다가 결국에는 하드코딩이 정답이라는 결론에 이르렀고, 모든 경우의 수를 생각하면서 가지치기를 해주는 코딩을 구현했다.

약 2시간 30분 걸림,,, 문제 자체는 어렵지 않은데 해결방법을 찾는데 오래 걸렸다.

def stair(arr):
    now_val = arr[0]
    visited = [0]*N
    for idx, val in enumerate(arr):
        # 현재층과 다음층이 같을경우
        if now_val == val:
            continue
        # 현재층과 다음층의 차이ㅏ 2이상일경우 바로 false
        elif abs(now_val - val) >= 2:
            return False

        # 현재에서 다음층으로 올라갈경우
        elif (now_val - val) == -1:
            # val의 idx를 기준으로 왼쪽 L개가 같아야함 그리고 L개 모두 사용안한자리
            for i in range(idx -1 , idx - L -1, -1):
                if 0 <= i < N and visited[i] == 0 and now_val == arr[i]:
                    visited[i] = 1
                else:
                    return False
        # 현재에서 다음층으로 내려갈경우
        elif (now_val - val) == 1:
            # val의 idx를 포함하여 오른쪽 L개가 같아야함 그리고 L개 모두 사용안한자리
            for i in range(idx, idx + L):
                # print(now_val)
                if 0 <= i < N and visited[i] == 0 and now_val-1 == arr[i]:
                    visited[i] = 1
                else:
                    return False

        # 한턴을 넘기면 현재의 값을 갱신
        now_val = val
    return True

N,L = map(int,input().split())
mapping = [list(map(int,input().split())) for _ in range(N)]
cnt = 0
# 행
for row in mapping:
    if stair(row):
        cnt +=1
# 열
for j in range(N):
    col = [row[j] for row in mapping]
    if stair(col):
        cnt +=1
print(cnt)