경사로

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

14890번: 경사로

문제요약:

n*n 크기의 배열이 있고, 각 행과 열이 길인데 이 수는 2n이다. 각 길은 같은 높이 (각 배열의 값이 높이) 일 때만 건널 수 있는데 이때 크기가 l의 경사로가 주어진다. 크기 l의 경사로는 같은 크기의 길이 l이상인 길이에 설치할 수 있으며 높이는 한번에 1까지만 올라갈수 있다. 경사로의 개수는 무제한일 때 2n개의 길중 건널수 있는 길의 수를 구하시오.

 

소요시간 ,제출횟수:

33분, 1회

난이도 골드3

 

코딩:

import sys
import math
input = sys.stdin.readline

n,l = map(int,input().split())

arr= [list(map(int,input().split())) for _ in range(n)]

ans = 0

def check(arr):
    global ans
    #각 길에 대해
    for row in arr:
    	#길에서 [길높이,갯수,길높이,갯수...] 순으로 배열만들기
        ex = 0
        num = 1
        temp = []
        for r in row:
            if r == ex:
                num+=1
            else:
                temp.append(num)
                ex = r
                num =1
                temp.append(r)
        else:
            temp.append(num)
        temp = temp[1:]
        
        
        for i in range(0,len(temp)-2,2):
        	#연속한 다른숫자의 크기차이가 1인지확인
            if abs(temp[i] - temp[i+2])!=1:
                break
            #그 둘중 작은것에 갯수가 L보다 큰지 확인하고 만약 크다면 갯수에서 l을 빼준다
            if temp[i] < temp[i+2] :
                if temp[i+1]>=l:
                    temp[i+1]-=l
                else:
                    break
            else:
                if temp[i+3]>=l:
                    temp[i+3]-=l
                else:
                    break
        #배열을 끝까지 확인했을 때 break 문에 걸리지 않았다면 == 조건에 위배되지 않았다면
        #길의 갯수 추가
        else:
            ans +=1
#행확인
check(arr)
#열확인
check(zip(*arr))
print(ans)

한 길에 대해 [숫자의 종류, 연속한 갯수...] 순으로 새 배열을 만들어줍니다.

가령 한 길이 [2,1,1,1,1,2,2,3] 이라고 되어있으면 2는 1개, 1은 4개, 2는 2개 , 3은 한개이므로

[2,1,1,4,2,2,3,1]과 같이 정렬해준뒤, 두개씩 건너 뛰며, 연속된 숫자의 종류가 1차이 인지 확인하고, 

1차이라면 그둘중 작은것에 길이 가 l보다 큰지 확인하고 만약 크다면 뒤에 비교를 위해 l만큼 빼줍니다.

그리고 중간에 조건에 만족하지 않는다면 break문으로 탈출하는데 탈출하지 않았다면 모든 조건을 만족하므로, 정답에 추가해줍니다. 그리고 zip(*)함수를 통해 열도 확인해 주었습니다.