문제 링크
https://www.acmicpc.net/problem/14890
🕒 Python 풀이시간: 40분
import math
n,l=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(n)]
def check(arr):
stack=0
prev=arr[0]
for i in range(n):
if prev!=arr[i]:
if arr[i]-prev==1 and stack>=l:
stack=0
elif prev-arr[i]==1:
t=arr[i:i+l]
if len(t)<l:
return False
if len(set(t))!=1:
return False
stack=-l
else:
return False
stack+=1
prev=arr[i]
return True
answer=0
for i in range(n):
tmp1=[]
tmp2=[]
for j in range(n):
tmp1.append(board[i][j])
tmp2.append(board[j][i])
if check(tmp1):
answer+=1
if check(tmp2):
answer+=1
print(answer)
🛤️ 경사로 설치 가능성 검사
2차원 배열에서 각 열과 행으로 이루어진 한 줄이 주어진 조건의 경사로를 이루고 있는지 물어보는 문제이다. 한 줄에 한해서 경사로를 검사할 때, 경사로의 길이가 주어지고 높이가 1이기 때문에 이 경사로를 무조건 겹치지 않고 놓을 수 있는 조건인지 확인해야 한다.
처음부터 끝까지 배열을 순회하면서 prev로 전의 칸을 기록해둔다. 전체의 경우, 놓을 수 있는 길이와 비교하기 위해 stack으로 +1을 늘려 기록하며 prev를 지금의 칸으로 갱신한다. 만약, 전의 칸과 지금의 칸의 높이가 다를 경우, 경사로를 지금의 조건으로 놓을 수 있을지를 검사한다.
만약 올라가는 경우라면 지금까지 쌓인 스택이 길이가 충분한지 확인하고 stack을 사용했기 때문에 0으로 초기화한다. 만약 내리막길을 놓아야하는 경우라면 앞의 l길이 만큼의 길이 높이가 같은지 같은 높이로 유지되는지를 확인한 후에 앞으로의 -l만큼의 stack을 계단으로 못쓰기 때문에(중첩 불가능) stack에서 -l을 해주면 된다.
이렇게 Python로 백준의 "경사로" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
