[백준] 14890번 경사로
문제 링크
https://www.acmicpc.net/problem/14890
문제 설명
- N, L, board 주어짐
- 가로 N개, 세로 N개의 길 중에서
- 지나갈수 있는 길의 개수 출력
- 높이 차이가 1일 경우
- 길이가 L인 경사로를 놓을 수 있으면 지나갈 수 있음
풀이
- 각 row에 대해서
- 높이가 한 칸 증가
- 이전 L칸 체크
- 높이가 한 칸 감소
- 이후 L칸 체크
느낀 점
- 높이 차이가 1일 경우
- 길이가 L인 경사로를 놓을 수 있으면 지나갈 수 있음
- 각 row에 대해서
- 높이가 한 칸 증가
- 이전 L칸 체크
- 높이가 한 칸 감소
- 이후 L칸 체크
느낀 점
구현이 상당히 까다로웠다 ㅠ
코드
def possible(line):
used = [False] * n
i = 0
while i+1 < len(line):
# 높이 같음
if line[i] == line[i+1]:
i += 1
# 높이 1 감소
elif line[i] == line[i+1] + 1:
# 범위를 벗어남
if i+1+l > len(line):
return False
# 높이가 다름
if len(set(line[i+1: i+1+l])) != 1:
return False
for j in range(i+1, i+1+l):
# 경사로 중복
if used[j]:
return False
used[j] = True
i += l
# 높이 1 증가
elif line[i] + 1 == line[i+1]:
# 범위를 벗어남
if i+1-l < 0:
return False
# 높이가 다름
if len(set(line[i+1-l: i+1])) != 1:
return False
for j in range(i+1-l ,i+1):
# 경사로 중복
if used[j]:
return False
used[j] = True
i += 1
else:
return False
return True
# init
import sys
read = sys.stdin.readline
n, l = map(int, read().split())
board = [list(map(int, read().split())) for _ in range(n)]
count = 0
# start
for i in range(n):
row = [board[i][j] for j in range(n)]
if possible(row):
count += 1
col = [board[j][i] for j in range(n)]
if possible(col):
count += 1
print(count)
Author And Source
이 문제에 관하여([백준] 14890번 경사로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-14890번-경사로
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
def possible(line):
used = [False] * n
i = 0
while i+1 < len(line):
# 높이 같음
if line[i] == line[i+1]:
i += 1
# 높이 1 감소
elif line[i] == line[i+1] + 1:
# 범위를 벗어남
if i+1+l > len(line):
return False
# 높이가 다름
if len(set(line[i+1: i+1+l])) != 1:
return False
for j in range(i+1, i+1+l):
# 경사로 중복
if used[j]:
return False
used[j] = True
i += l
# 높이 1 증가
elif line[i] + 1 == line[i+1]:
# 범위를 벗어남
if i+1-l < 0:
return False
# 높이가 다름
if len(set(line[i+1-l: i+1])) != 1:
return False
for j in range(i+1-l ,i+1):
# 경사로 중복
if used[j]:
return False
used[j] = True
i += 1
else:
return False
return True
# init
import sys
read = sys.stdin.readline
n, l = map(int, read().split())
board = [list(map(int, read().split())) for _ in range(n)]
count = 0
# start
for i in range(n):
row = [board[i][j] for j in range(n)]
if possible(row):
count += 1
col = [board[j][i] for j in range(n)]
if possible(col):
count += 1
print(count)
Author And Source
이 문제에 관하여([백준] 14890번 경사로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-14890번-경사로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)