[파이썬] 백준 14890 : 경사로 (골드3)

[파이썬] 백준 14890 : 경사로 (골드3)

14890번: 경사로

 

---

문제

---

풀이

0. 방향성 생각

1. 경사2 -> 불가능

2. 범위 바깥 -> 불가능

3. 경사로 이미 설치 -> 불가능

4. 경사로 아래 평지 아님 -> 불가능

4개 다 아니면 count

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()

n,l = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
arr_tr = list(zip(*arr))

행은 입력 그대로 넣기.

열 체크할 때 전치행렬 만들기.

2. 함수 정의

def check(road):
    
    slope = [0]*n
    
    for i in range(n-1):
        
        if abs(road[i+1]-road[i]) > 1:
            return 0
        
        if road[i+1]-road[i] > 0:
            for step in range(l):
                if i-step < 0 or slope[i-step] or road[i+1] != road[i-step]+1:
                    return 0
                slope[i-step] = 1
        
        if road[i+1]-road[i] < 0:
            for step in range(1,l+1):
                if i+step >= n or slope[i+step] or road[i]-1 != road[i+step]:
                    return 0
                slope[i+step] = 1
    return 1

경사로 설치유무 slope 만들기

1. 경사가 2가 넘어가면 설치 불가

2. 오르막인 경우 : 경사로 설치 시 범위 바깥이면 불가능 / 설치됐으면 불가능 / 경사로 아래가 평지가 아니면 불가능

오르막인 경우 현재 위치 i에서 다음위치 step을 뒤쪽으로 밟는다. (올라가려면 현재 위치에서 아래로 설치해야함)

3. 내리막인 경우도 마찬가지이다.

내리막인 경우 현재 위치 i에서 다음 위치 step을 앞쪽으로 밟는다. (내려가려면 현재 위치에서 앞으로 설치해야함)

모두 통과했으면 return 1

 

3. 출력

answer = 0
for row in arr:
    answer += check(row)
for col in arr_tr:
    answer += check(col)

print(answer)

행따로, 열따로 받아서 정답에 추가.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

n,l = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
arr_tr = list(zip(*arr))

def check(road):
    
    slope = [0]*n
    
    for i in range(n-1):
        
        if abs(road[i+1]-road[i]) > 1:
            return 0
        
        if road[i+1]-road[i] > 0:
            for step in range(l):
                if i-step < 0 or slope[i-step] or road[i+1] != road[i-step]+1:
                    return 0
                slope[i-step] = 1
        
        if road[i+1]-road[i] < 0:
            for step in range(1,l+1):
                if i+step >= n or slope[i+step] or road[i]-1 != road[i+step]:
                    return 0
                slope[i+step] = 1
    return 1

answer = 0
for row in arr:
    answer += check(row)
for col in arr_tr:
    answer += check(col)

print(answer)

 

코멘트

골3급은 아닌듯한데