문제
n,n 지도, 각 칸은 지도 높이 값
지나갈 수 있는 길이 몇개인지 확인
경사로를 놓아서 지나갈 수 있는지 생각해보자.
내 코드
import sys
n,L = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
res = 0
# ! 먼저 행 먼저 판단
for i in range(n):
count = 1 # 유효 길이
for j in range(n-1): # 현재 값과 다음 값을 비교해야 하므로 한칸 작게 설정
if abs(g[i][j] - g[i][j+1]) > 1: break # 높이 차가 1보다 크면 안된다.
if g[i][j] == g[i][j+1]: # 다음 좌표랑 동일하면 (평지)
count += 1 # 유효 길이 증가
elif g[i][j] + 1 == g[i][j+1]: # 오르막
if count >= L: # 가능한 경우
count = 1 # 다시 1로 초기화 # 본인 좌표 유효길이 다시 시작해야 하므로
else:
break
elif g[i][j] == g[i][j+1]+1: # 내리막인 경우
if count < 0: break # 유효길이가 0보다 같거나 커야해 이유는 0보다 작은 경우는 경사로가 겹치기 때문
count = -(L-1)
else: # 반복문을 다 돌았다는 건 가능한 경우가 될 수 있따.
if count >= 0:
# print(f"{i}번쨰 행은 추가 가능")
res += 1
# 열에 대해서도 똑같이 판단
for j in range(n):
count = 1
for i in range(n-1):
if abs(g[i][j] - g[i+1][j]) > 1: break
if g[i][j] == g[i+1][j]: # 같은 경우는 +1
count += 1
elif g[i][j] + 1 == g[i+1][j]: # 오름
if count >= L: # 가능한 경우
count = 1
else:
break
elif g[i][j] == g[i+1][j] + 1: # 내림
if count < 0: break
count = -(L-1)
else: # 반복문 다 돈 것은 가능한 경우가 될 수 있음
if count >= 0:
# print(f"{j}번째 열은 추가 가능")
res += 1
print(res)코멘트
처음에 어떻게 접근해야 하는지 조차 생각하지 못했다. 결국 답을 확인..
경사로는 올라갈 수 있도록, 혹은 내려갈 수 있도록 놓아 길을 만들 수 있다.
경사로는 무한정 깔 수 있지만, 이미 기존에 깔았던 칸에는 경사로를 놓을 수 없음.
실제로 삼성A형 시뮬 유형 문제는 일단 실제로 문제를 계속 읽으면서 또 이해하면서 내가 직접 해봐야 한다. 이 경우 가능한 경우를 보면서 어느 칸에 경사로를 놓았을 때 가능한지 파악했어야 했다.
-> 그리고 높이가 낮은 칸에만 길이가 L인 경사로를 놓으면 되는구나. 가장 먼저 이해하고 그렇다면 이걸 어떻게 카운트하지 ? 로 이어졌어야 했다.
-> 나는 문제를 잘못 이해해서 2 3 이 경우에 올라가는 두 칸에 놓아야 한다고 생각..
하지만 그림에도 나와있었는데.. 문해력 ;
어떻게 풀 수 있을까?
n개의 가로 길, n개의 세로 길 존재
이 중에 n개의 세로길을 n개의 가로길로 변환해주면 문제를 조금 더 쉽게 접근할 수 있다.
-> 문제를 풀면서 이런 생각을 하는 날이 와야겠다...
물론 가로 체크하고 세로 체크해도 문제 없음
그렇다면 경사로를 어떻게 적절히 놓아서 이 길을 갈 수 있는지 없는지를 판단하는지 알아보자.
- 시작 칸의 유효한 가로 길이는 1이다
-> 이렇게 생각해야 하는 이유는 L은 1부터 가능.
즉 현재 칸의 유효 값이 얼마인지에 따라서 경사로를 놓을 수 있는지, 없는지를 판단할 예정 - 시작점을 1로 놓고 다음 칸과 비교 시작
2-1. 만약3->2로 변경이 되었다면 내리막 이다.
2-2. 내리막을 만나면 이전의 유효거리가 0보다 큰지 확인
2-3 이전까지의 유효거리가 0보다 크다면 -> (이전까지의 유효거리와는 상관없이) 1-L로 현재 유효 값(거리)을 변경해준다.(0보다 작으면 경사로 겹치는 거니깐)
-> 그 이유는3->2로 변경, L=2 인 상황에서 3 뒤로 2칸의 2가 존재해야만 한다. 즉 2칸을 미리 사용했다는 의미로 현재 내 공간은 1이니까 (어느 칸이든 일단 본인 자리) 그렇기에 -(L-1)값을 가지고 있다는 것이다. - 만약 현재 칸과 다음 칸이 같은 경우
2->2: 평지이다.
3-1. 평지를 만나면 이전 유효한 가로길에 +1을 한다. (왜냐하면 그대로 이어지기 때문에 +1) - 만약
2->3으로 변경이 되었다면 오르막이다.
4-1. 오르막을 만나면, 이전 유효한 길이가 L보다 작으면 경사로를 만들 수 없다.
4-2. 만약 오르막 경사로를 놓을 수 있다면 본인 칸 값 다시 1로 시작.
-> 경사로를 만드는 것이 가능하면 유효 길이를 1로 초기화
이 과정을 반복해서 행 또는 열의 전체 길이를 살펴봤을 때 유효 값이 0 이상이어야만 한다. 그렇다면 해당 행 또는 열은 경사로를 놓아서 길을 만들 수 있다.
좌표에 값을 넣어서 가능한지 안한지 판단... 이런 유형을 또 풀어보자.
