https://www.acmicpc.net/problem/14890
#14890: 램프
첫 번째 줄은 N(2 ≤ N ≤ 100) 및 L(1 ≤ L ≤ N)을 제공합니다.
두 번째 줄부터 시작하여 N 줄로 지도를 제공합니다.
각 셀의 높이는 10 이하의 자연수입니다.
www.acmicpc.net
문제는 각 행 또는 열을 전달할 수 있는지 여부를 결정해야 한다는 것입니다.
구현하기만 하면 됩니다.
내가 원래 작성한 코드는 다음과 같습니다.
import sys
input = sys.stdin.readline
def is_all_same_height(heights):
for i in range(len(heights) - 1):
if heights(i) !
= heights(i + 1):
return False
return True
def is_all_same_column(board, c):
for r in range(len(board) - 1):
if board(r)(c) !
= board(r + 1)(c):
return False
return True
def solution(n, k, board):
answer = 0
for row in board:
checked = (False for _ in range(n))
if is_all_same_height(row):
answer += 1
else:
for c in range(n - 1):
if row(c) == row(c + 1):
continue
if row(c) + 1 == row(c + 1):
for nc in range(c, c - k, -1):
if nc < 0 or checked(nc) or row(nc) !
= row(c):
break
else:
nc = c - k + 1
for i in range(nc, c + 1):
checked(i) = True
continue
break
elif row(c) == row(c + 1) + 1:
for nc in range(c + 1, c + 1 + k):
if nc >= n or checked(nc) or row(nc) !
= row(c + 1):
break
else:
nc = c + 1 + k
for i in range(c + 1, nc):
checked(i) = True
continue
break
else:
break
else:
answer += 1
for c in range(n):
checked = (False for _ in range(n))
if is_all_same_column(board, c):
answer += 1
else:
for r in range(n - 1):
if board(r)(c) == board(r + 1)(c):
continue
if board(r)(c) + 1 == board(r + 1)(c):
for nr in range(r, r - k, -1):
if nr < 0 or checked(nr) or board(nr)(c) !
= board(r)(c):
break
else:
nr = r - k + 1
for i in range(nr, r + 1):
checked(i) = True
continue
break
elif board(r)(c) == board(r + 1)(c) + 1:
for nr in range(r + 1, r + 1 + k):
if nr >= n or checked(nr) or board(nr)(c) !
= board(r + 1)(c):
break
else:
nr = r + 1 + k
for i in range(r + 1, nr):
checked(i) = True
continue
break
else:
break
else:
answer += 1
return answer
N, L = map(int, input().split())
_board = ()
for _ in range(N):
_board.append(list(map(int, input().split())))
print(solution(N, L, _board))
사실 지금 돌이켜봐도 무슨 일이 있었는지 알기 힘듭니다.
유테코 프렙때부터 이런 더러운 코드 쓰는게 마음속으로 싫었는데 코테의 특성상 먼저 구현해보고 싶었기 때문에 더럽다는걸 알고 안주했습니다.
코드의 요지는 대충 행과 열의 순회 가능 여부를 결정하는 코드가 다릅니다.
예. 행과 열에 액세스하는 인덱스 방법이 다르기 때문에 별도로 생성됩니다.
그러나 다른 사람들의 솔루션을 보면 실제로 더 쉬운 방법이 있습니다.
행과 열을 1차원 배열로 간주하는 것이므로 어떤 인덱싱 방법을 사용해도 동일합니다.
즉, 열을 행으로 취급하십시오!
Python의 for 문 사용
board = (
(1, 2, 3, 4),
(5, 6, 7, 8),
(9, 10, 11, 12),
(13, 14, 15, 16)
)
column = (board(i)(0) for i in range(4))
이와 같이 컬럼을 1차원 리스트, 즉 행으로 추출할 수 있다.
이렇게 하면 행과 열을 결정하기 위해 별도의 코드를 작성하는 대신 하나의 코드를 사용하여 행과 열을 결정할 수 있습니다.
import sys
input = sys.stdin.readline
def check_path(path, k):
length = len(path)
check = (0 for _ in range(length))
for i in range(length - 1):
if abs(path(i) - path(i + 1)) > 1:
return False
if path(i) + 1 == path(i + 1):
for j in range(i, i - k, -1):
if j < 0 or check(j) or path(j) !
= path(i):
return False
check(j) = 1
continue
if path(i) == path(i + 1) + 1:
for j in range(i + 1, i + 1 + k):
if j >= length or check(j) or path(j) !
= path(i + 1):
return False
check(j) = 1
return True
def solution(n, k, board):
answer = 0
# 행에 대한 판단
for row in board:
if check_path(row, k):
answer += 1
# 열에 대한 판단
for c in range(n):
if check_path((board(i)(c) for i in range(n)), k):
answer += 1
return answer
N, L = map(int, input().split())
_board = ()
for _ in range(N):
_board.append(list(map(int, input().split())))
print(solution(N, L, _board))
구현이라는 프로젝트를 다룰 때 이렇게 단순화하고 생각하는 것이 중요한 것 같습니다.
그렇지 않으면 시간이 너무 오래 걸리는 것 같습니다.