[백준14890번] 경사로(파이썬)

https://www.acmicpc.net/problem/14890

14890번: 경사로

문제가 상당히 길기 때문에

문제에서 주어진

지나가는 길의 케이스만을 가져와봤습니다.

(자세한 문제는 링크참조해주세요)

모두 같은 수가 있거나

경사로를 만들 수 있다면

지나갈 수 있는 길이라는 의미.

여기서 제가 다소 해맸던 부분은

아래에서 위로 올라가는 부분이었습니다.

문제에서 주어진 예제2의 경우입니다.

저는 초반에 자꾸

[3 2 2 2 3 3]이 카운트가 되었습니다.

????

이거 아무 문제없는데 왜?

라고 생각하실 수 있겠지만

이 경우에는 경사로가 겹치게 됩니다.

이런 식으로 겹치기 때문에

이 케이스는 생략을 해줘야합니다.

 

#백준14890 경사로

N,L=map(int,input().split())

road=[]
for i in range(N):
  road.append(list(map(int,input().split())))

#road_two로 세로로 볼 때의 길도 다 받음.
road_two=[[]for _ in range(N)]
for i in range(N):
  for j in range(N):
    road_two[i].append(road[j][i])

answer=0

def solve(path):
  global answer
  for i in range(N):
    get_a=1
    now=path[i][0]
    repeat=1
    j=1
    while j<N:
      if now==path[i][j]:
        repeat+=1
        j+=1
      else:
        if abs(now-path[i][j])>1:#경사로는 1차이나야 만들 수 있으므로, 그 이상은 다 버림.
          get_a=0
          break
        if now>path[i][j]: #큰거에서 작은 것을 만났을 때
          under=path[i][j]
          n_repeat=1
          for k in range(j+1,N):
            if path[i][k]==under:
              n_repeat+=1
            else:
              break
          if n_repeat>=L:
            #print("n_repeat")
            #print(n_repeat)
            now=under
            repeat=0
            j+=L #L이 최소이므로, L만큼 이동해준다.
            #print("now_on")
            #print(j)
            continue
          else:
            get_a=0
            break
        if now<path[i][j]: #작은거에서 큰거를 만났을 때
          if repeat>=L:
            now=path[i][j]
            repeat=1
            j+=1
          else:
            get_a=0
            break
    if get_a==1:
      answer+=1
      #print(path[i])


solve(road)
#print('next')
solve(road_two)
print(answer)

 

구글링을 해보니,

제가 만든 코드의 경우

큰 거에서 작은 것을 만났을 때가

다소 복잡한 케이스입니다.

저는 코드를 짤 때

'작은 게 얼마만큼 반복되는 지 보고

최소 길이인 L만큼 경사로를 만든다'

라는 개념으로 접근을 했습니다.

물론 통과는 되었던 코드였지만

제 스스로 공부를 더 하기 위해

구글링 후에 공부를 더 할 수 있었던 문제였습니다.

(*내가 맞게 푼 문제도

다른 사람의 코드를 보면

공부할 게 많다는 걸 느낄 수 있었습니다.

함수를 쓰는 방식이라든가

코드를 쓰는 방식이라든가

여라기지로 공부할 수 있는게 많다는 걸

이 문제를 통해 배웠습니다.)

 

+++++

 

#백준 14890번 경사로

N,L=map(int,input().split())

graph=[list(map(int,input().split())) for _ in range(N)]

#길을 가로 세로 전부 다 본다.

road=0
#가로줄을 먼저 본다
for x in range(N):
    now=graph[x][0]
    flag=0
    length=1
    y=1
    while y<N:
        #같은 걸 만나는 경우
        if graph[x][y]==now:
            length+=1
        #더 작은 걸 만나는 경우
        elif graph[x][y]==now-1:
            t_n=graph[x][y]
            t_length=1
            ny=y+1
            #작은 게 L이상 만족하는지 보기
            while ny<N:
                if graph[x][ny]==t_n:
                    t_length+=1
                else:
                    break
                ny+=1

            if t_length>=L:
                now=t_n
                length=0
                y=y+L-1
            else:
                flag=1
                break
        #더 큰 걸 걸 만나는 경우
        elif graph[x][y]==now+1:
            #지금께 길이가 L이상 만족한다면 길이 됨.
            if length>=L:
                now=graph[x][y]
                length=1
            else:
                flag=1
                break
        #그 외의 경우는 끝냄
        else:
            flag=1
            break
        y+=1
    if flag==0:
        road+=1

#세로로 보기
for y in range(N):
    now = graph[0][y]
    flag = 0
    length = 1
    x=1
    while x<N:
        # 같은 걸 만나는 경우
        if graph[x][y] == now:
            length += 1
        # 더 작은 걸 만나는 경우
        elif graph[x][y] == now - 1:
            t_n = graph[x][y]
            t_length = 1
            nx = x + 1
            # 작은 게 L이상 만족하는지 보기
            while nx < N:
                if graph[nx][y] == t_n:
                    t_length += 1
                else:
                    break
                nx += 1

            if t_length >= L:
                now = t_n
                length = 0
                x=x+L-1
            else:
                flag = 1
                break
        # 더 큰 걸 걸 만나는 경우
        elif graph[x][y] == now + 1:
            # 지금께 길이가 L이상 만족한다면 길이 됨.
            if length >= L:
                now = graph[x][y]
                length = 1
            else:
                flag = 1
                break
        # 그 외의 경우는 끝냄
        else:
            flag = 1
            break
        x+=1
    if flag == 0:
        road += 1

print(road)

다시 푼 코드

이 코드는 우직하게

x,y따로따로 구해서

가로 새로를 구해준 케이스입니다.

 

https://pacific-ocean.tistory.com/368

[백준] 14890번(python 파이썬)

https://chldkato.tistory.com/154

백준 14890 경사로 (파이썬)

https://ryu-e.tistory.com/108

[Python] 백준 14890 경사로

공부할만한 다양한 풀이입니다.