경사로

14890. 경사로

In [16]:

from sys import stdin
# import numpy as np

# plot = lambda a: print(np.array(a))
stdin = open('data/slope.txt')
input = stdin.readline
n, L = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
a

[[3, 3, 3, 3, 3, 3],
 [2, 3, 3, 3, 3, 3],
 [2, 2, 2, 3, 2, 3],
 [1, 1, 1, 2, 2, 2],
 [1, 1, 1, 3, 3, 1],
 [1, 1, 2, 3, 3, 2]]

Submitted Code

My code

깔끔하지 못하게 풀어서, Discuss를 통해 다른사람의 코드를 보고 배우겠다.

In [19]:

from sys import stdin
# import numpy as np

# plot = lambda a: print(np.array(a))
stdin = open('data/slope.txt')
input = stdin.readline
n, L = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]

# plot(a)

def solution(a, L):
    def check(line):
        tmp, cnt, i = line[0], 1, 1
        while 0 <= i < n:
            if line[i] == tmp:
                cnt = cnt + 1 if cnt < L else cnt
                i += 1
            else:
                if abs(line[i] - tmp) > 1:
                    return False
                if line[i] - tmp == 1 and cnt == L:  # up
                    cnt, tmp = 1, line[i]
                    i += 1
                elif tmp - line[i] == 1 and n - i >= L:  # down
                    cnt, tmp = 1, line[i]
                    i += 1
                    while (0 <= i < n and cnt < L):  
                        if line[i] == tmp:
                            cnt += 1
                            i += 1
                        else: return False
                    cnt = 0
                else:
                    return False
        return True

    ans = 0
    for i in range(n):  # row cases
        if check(a[i]):
            ans += 1

    at = [[a[i][j] for i in range(len(a))] for j in range(len(a[0]))]

    for j in range(n):  # column cases
        if check(at[j]):
            ans += 1
    return ans

solution(a, L)

3

Discuss

우선 row 와 col 에대해서 d를 사용하여 분리하여 계산하도록 한다.

다음과 같은 사항을 통해 check함수를 만든다.

• 길의 높이가 같다면 (d == 0), 카운트를 1 증가시킨다. 카운트는 경사로의 길이와 비교하기 위해 필요하다.
• 올라가는 경사로라면 (d == 1), 카운트가 경사로의 길이 L 이상인지 확인한다. 카운트가 L 이상이라면, 경사로를 놓을 수 있는 경우이므로, 카운트를 1로 초기화시킨다.
• 내려가는 경사로라면 (d == -1), 카운트가 0 이상인지 확인한다. 0 이상이라면, 카운트를 경사로의 길이 L만큼을 음수로 만든다. 만약 카운트가 음수라면, 내려가는 경사로를 만들고 있는 중이므로, 경사로를 놓을 수 없다.

출처: https://rebas.kr/788 [PROJECT REBAS]

In [15]:

def solution(a, L):
    n, ans = len(a), 0
    def check(i, kind):
        nonlocal ans
        cnt = 1
        for j in range(n - 1):
            d = a[i][j + 1] - a[i][j] if kind else a[j + 1][i] - a[j][j]
            if d == 0: cnt += 1
            elif d == 1 and cnt >= L: cnt = 1
            elif d == -1 and cnt >= 0: cnt = -L+1 
            else: return
        if cnt >= 0: ans += 1

    for i in range(n):
        check(i, 1)  # row
        check(i, 0)  # col
   
    return ans

solution(a, L)

3