[Gold III]
https://www.acmicpc.net/problem/14890
14890번: 경사로
첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.
www.acmicpc.net
풀이
골드 3짜리 빡구현 문제..
한 줄(행/열) 마다 돌려가며 check.
모든 칸에 대해 돌려봐도 100x100 = 10,000 이므로, Brute-Force로 접근 가능.
한 줄의 모든 칸에 대해,
다음 칸과 1 이상 차이나면 break처리.
다음 칸과 숫자가 동일하면 패스.
다음 칸보다 더 작다면, 그 이전 L개의 칸이 동일한 지 확인.
다음 칸보다 더 크다면, 그 이후 L개의 칸이 동일한 지 확인.
install 배열로 그 칸에 경사로를 설치했는 지 확인.
모든 반복문을 문제없이 통과했다면, result++
N, L = map(int, input().split())
M = []
for _ in range(N):
M.append(list(map(int, input().split())))
result = 0
install = []
for _ in range(N):
install.append([False]*N)
# 가로(행)의 가능한 길
for r, row in enumerate(M):
flag = True
for i in range(N-1):
if abs(row[i]-row[i+1]) > 1:
flag = False
break
if row[i] == row[i+1]+1: # 왼쪽이 크면
for k in range(1, L+1):
# index out of range
if not 0 <= i+k < N:
flag = False
break
# 이후 L개동안 같은 숫자가 아니라면
if row[i] != row[i+k]+1 or install[r][i+k]:
flag = False
break
if flag:
for k in range(1, L+1):
install[r][i+k] = True
if row[i] == row[i+1]-1: # 오른쪽이 크면
for k in range(0, L):
# index out of range
if not 0 <= i-k < N:
flag = False
break
# 이전 L개가 같은 숫자가 아니라면
if row[i-k] != row[i+1]-1 or install[r][i-k]:
flag = False
break
if flag:
for k in range(0, L):
install[r][i-k] = True
if flag:
result += 1
install = []
for _ in range(N):
install.append([False]*N)
# 세로(열)의 가능한 길
for r in range(N):
row = []
for k in range(N):
row.append(M[k][r])
flag = True
for i in range(N-1):
if abs(row[i]-row[i+1]) > 1:
flag = False
break
if row[i] == row[i+1]+1: # 왼쪽이 크면
for k in range(1, L+1):
# index out of range
if not 0 <= i+k < N:
flag = False
break
# 이후 L개동안 같은 숫자가 아니라면
if row[i] != row[i+k]+1 or install[i+k][r]:
flag = False
break
if flag:
for k in range(1, L+1):
install[i+k][r] = True
if row[i] == row[i+1]-1: # 오른쪽이 크면
for k in range(0, L):
# index out of range
if not 0 <= i-k < N:
flag = False
break
# 이전 L개가 같은 숫자가 아니라면
if row[i-k] != row[i+1]-1 or install[i-k][r]:
flag = False
break
if flag:
for k in range(0, L):
install[i-k][r] = True
if flag:
result += 1
print(result)