14890 - 경사로

 

---

 

문제

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

14890번: 경사로

 

풀이

 

나는 현재 위치 기준으로, 다음 변하는 값이 큰 값인지, 작은 값인지에 따라 분기를 나누었다.

(만약 한 칸 차이가 아니라면 무조건 안되므로 바로 False!)

 

큰 경우를 살펴보면 예로, 배열은 [2,2,3,3] l은 2 라고 해보자.

2의 개수를 계속 카운트 하다가, 3이 나오면 경사로는 2에 설치해야한다.

따라서 2의 개수가 l개 이상인지 판단하면 된다.

만약 경사로를 설치할 수 있다면 현재값을 3으로 이동시켜주고 로직을 반복시키면 된다.

 

작은 경우를 살펴보자,

다음값이 작은 경우에는 다음 값의 개수가 l개가 되는 순간 바로 경사로를 설치하면 된다.

그리고 경사로 설치한 다음값을 현재값으로 갱신해서 로직을 반복하면 된다.

 

근데 내 로직같은 경우엔 문제가 조금 있었다. 이 로직은 아래 예를 생각하고 짠것이다. (l은 모두 2라고 가정하겠다.)

1.

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

이 경우에는 2가 작은값으로 2개가 연속하고 있다. 따라서 경사로를 설치후에 세번째 2로 현재값을 갱신해준다.

이렇게 된다면 내 생각대로 동작하는데, 문제는 아래 예시이다.

 

2.

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

이 경우에도 2가 2개라 경사로를 설치하는데 바로 3으로 이동하게 된다. 이 경우 경사로를 더 설치할 공간이 없기에 False인데, 현재값을 3으로 바로 갱신해서 로직을 실행하면 문제없이 통과가 되었다.

 

3.

[3, 3, 2, 2, 1]

이 경우 또한 비슷하다. 그 다음값이 작다는 걸 인지할 필요가 있는데 2에서 경사로를 설치한 후, 바로 현재값을 1로 갱신해주기 때문에 그냥 통과 시켜 버린다.

 

따라서 경사로 설치후에 다른 값이 나올 경우를 예외처리해주면 된다.

 

두번째 케이스를 생각해보면 내가 경사로를 다 설치했는데 큰 값이 나온다? -> 무조건 실패다. 경사로를 설치할 공간이 없다.

 

세번째 케이스 같은 경우에는 현재값을 2로 하고 다음값이 작다는걸 인지시켜줄 필요가 있다. 따라서 현재값을 경사로 설치 다음 값이 아닌, 경사로 마지막 위치로 설정해주면 된다. 그러면 기존 로직대로 다음값이 작다는걸 알게 되고, 다음 값의 연속된 개수에 따라 경사로 설치여부를 판단할 수 있다.

 

 

입력 같은경우에는 n * n 배열을 받고, 그걸 1차원 배열로 파싱? 해서 다리를 지날 수 있는지 판단하는 함수를 하나 만들어서 풀이했다.

 

 

 

코드

# 한 줄 마다 검사하자.
def solution(arr, l):

    length = len(arr)

    i = 0

    #초기값 설정
    now = arr[0]
    n_count = 0
    runway = True

    while i < length:
        # 우선 현재 값과 같은개 몇개 있는지 체크한다.
        while i < length and arr[i] == now:
            n_count += 1
            i += 1

        # 범위 안에 들어갈 경우
        if i < length:
            # 내 기준으로 다음값이 1 크다면
            # 현재 레벨에서 경사로를 설치해주어야 한다.
            if now + 1 == arr[i]:
                # 경사로를 설치할 충분한 공간이 있는지 확인한다.
                if n_count >= l:
                    # 경사로 설치 및 다음 값으로 이동한다.
                    now = arr[i]
                    n_count = 0
                else:
                    runway = False
                    break

            # 내 기준으로 다음값이 1 작다면
            # 다음 레벨에서 경사로를 설치해주어야 한다.
            elif now - 1 == arr[i]:
                # 다음 레벨이 l개 연속하고 있을 경우, 바로 경사로를 설치해준다.
                # 이후 now 값을 경사로 다음값으로 이동시켜 준다.
                next_value = arr[i]
                next_count = 0
                while i < length and next_value == arr[i]:
                    next_count += 1
                    i += 1
                    # 만약 경사로 설치할 수 있는 공간이 있다면
                    if next_count == l:
                        break

                if next_count == l:
                    if i < length:
                        # 경사로를 설치했는데, 다음값이 큰 값이면 설치 자체가 불가능
                        if arr[i] > next_value:
                            runway = False
                            break
                        # 만약 작은값이라면 작은 분기로 빠질 수 있게 i-1 을 now로 위치해준다.
                        elif arr[i] < next_value:
                            now = arr[i-1]
                            n_count = 0
                        # 같은 값이라면 그대로 초기화
                        else:
                            now = arr[i]
                            n_count = 0
                else:
                    runway = False
                    break

            # 1작거나, 1큰게 아니라면 아예 실패
            else:
                runway = False
                break

        # 범위 자체가 벗어나면 break
        else:
            break
    return runway



n, l = map(int, input().split())
board = [ list(map(int, input().split())) for _ in range(n) ]
answer = 0
for i in range(2):
    for j in range(n):
        temp = []
        for k in range(n):
            if i == 0 : temp.append(board[j][k])
            else : temp.append(board[k][j])
        if solution(temp, l): answer += 1

print(answer)

 

후기

 

첫날에 문제를 잘못이해해서 완전 난잡한 코드를 만들었었다. 두시간 가까이 풀었는데, 테스트 케이스는 맞았으나 반례들이 속출했다. 수정하기에도 너무 스파게티라서, 다음날 정신을 가다듬고 코드를 다시 작성했다. 

 

기존에는 2차원 배열을 한번에 받아 처리하는 로직이라 인덱싱부터 훨씬 복잡하고 헷갈렸는데, 1차원 배열을 받는 함수를 만들어서 판단하는 구조로 바꾸었다. 덕분에 코드도 깔끔해졌고, 작성하면서 혼란도 훨씬 줄었다.

 

물론 난이도가 조금 있는 구현문제이나, 단순 구현이라 조금 더 깔끔하고, 빠르게 풀 수 있도록 구현 문제를 꾸준히 연습해야 할 거 같다. 그리고 문제를 제발 꼼꼼히 읽자. 첫날에 제대로 읽었더라면 이렇게 돌아오지 않았을수도 있다.