[python] 14890 - 경사로

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

14890번: 경사로

정답률 55.699%

난이도 골3

경우의 수 잘 나눠야함(경사로 못치는 경우 잘 생각하기)

 

+ 열 검사하기 귀찮아서 입력값을 행과 열 바꿔서 다른 배열에 저장해놓은 뒤, 행 검사 함수에 넣음

---

코드 설명

※ 주의할 점

• 높이가 1 감소하는 경우 중 같은 높이의 블럭이 L개 나오기 전에 라인이 끝날 때
• 높이가 1 감소하는 경우에서 이미 경사로 놓은 곳에 높이 1 증가하는 경우로 경사로 다시 놓기
  (ex. 3 3 2 2 3 3)
• 두칸 이상 차이나면 무조건 못지나감

def find_path(line):
    same = 1                                # 여태까지 같은 높이의 연속된 칸이 몇개인지
    check = 0                               # j보다 j+1이 낮을 때를 기준으로 같은 높이의 칸이 몇개인지
    already = []							# 이미 울타리 쳐진 곳
    for j in range(N - 1):
        # 높이 같을때
        if line[j] == line[j + 1]:
            same += 1
            # 앞>뒤 블럭이 발생한 후
            if 1 <= check < L:
                check += 1
                already.append(j + 1)       # 울타리가 쳐질 인덱스 
                if check == L:
                    check = 0
        
        # 앞블럭이 더 높았는데 L만큼 같은 높이의 칸이 나오기 전에 다른높이가 나왔을때 
        elif 1 <= check < L:
            return 0
        
        # 앞블럭이 높을때
        elif line[j] == line[j + 1] + 1:
            same = 1
            check = 1
            already.append(j + 1)           # 울타리가 쳐질 인덱스
            
        # 뒷블럭이 높을때
        elif line[j] == line[j + 1] - 1:
            if same < L:                    # 이미 지나쳐온 같은높이의 블럭 개수가 L보다 작을때
                return 0
            elif j - L + 1 in already:      # 이미 울타리가 쳐져있을때
                return 0
            same = 1
            
        
        # 두칸이상 차이날때
        else:
            return 0

    if 1 <= check < L:      # 앞>뒤의 경우 중 L을 다 못채우고 line이 끝날떄
        return 0

    return 1 # 무사히 건넘


N, L = map(int, input().split())
rot_baord = [[] for _ in range(N)]      # 행과 열이 바뀐 입력값
ans = 0
for i in range(N):
    temp = list(map(int, input().split()))
    for j in range(N):
        rot_baord[j].append(temp[j])
    if find_path(temp):                 # 그 줄이 지나갈수 있는지 True/False 반환
        ans += 1

for temp in rot_baord:                  # 원본 입력값에서는 열
    if find_path(temp):
        ans += 1

print(ans)

 

---

코드 결과