2019.02.20) 백준 1520번 풀이 (PyPy3)

이번엔 소스코드가 2개다

위에 소스코드는 값을 리턴하는 방향으로 짜서 코드 길이가 최적화되있고

아래는 dp에 저장해 불러오는 방향으로 만들어서 이해하기 쉽다(?)

이 문제는 역대급으로 시간초과와 틀렸습니다가 많이 났다.

주인장이 겪은 큰 문제들만 나열하자면

1. 탐색이 왼쪽 오른쪽 아래쪽만 하면 되는줄 알았다

이건 문제 예시가 좀 잘못했다. 구글링하며 보니까 다른사람들은 왜 위까지 탐색하지 이런 의문을 가지면서 알았다.

계단은 위에서 아래로 내려와야하는거 아닌가? 라고 생각했는데 단순히 숫자만 그렇게 생각하자 였을 줄이야;;

이거 때문에 틀렸습니다가 떴다.

(30%에서 틀렸습니다.)

2. 종점일땐 확실하게 끊어라

종점 옆에 종점보다 작은 수가 있으면 이제 숫자가 종점을 탈출한다. 이거때문에 시간초과가 떴다.

(19%에서 23% 올라가는 척하며시간초과)

1번째 코드

a, b = map(int, input().split(' '))
l = list()
for i in range(a):
    l.append(list(map(int, input().split(' '))))
 
# dp할 배열 생성
success = [[None for i in range(b)] for j in range(a)]
 
 
def s(i, j):
    # 이부분도 중요함 여길 안막으면 종점에 가서도 역으로 재탐색함(이거도 애매했음)
    if i == a - 1 and j == b - 1:
        return 1
    # 이미 탐색 됬다면(None 이 아니니까) 그냥 리턴
    if success[i][j] is not None:
        return success[i][j]
 
    # 탐색 시작시 초기화
    success[i][j] = 0
 
    # 상하좌우 전부로 움직일 수 있음(이거때문에 계속 틀림)
    if j < b - 1 and l[i][j] > l[i][j + 1]:
        success[i][j] += s(i, j + 1)
    if j > 0 and l[i][j] > l[i][j - 1]:
        success[i][j] += s(i, j - 1)
    if i < a - 1 and l[i][j] > l[i + 1][j]:
        success[i][j] += s(i + 1, j)
    if i > 0 and l[i][j] > l[i - 1][j]:
        success[i][j] += s(i - 1, j)
 
    return success[i][j]
 
 
print(s(0, 0))
 

2번째 코드

a, b = map(int, input().split(' '))
l = list()
for i in range(a):
    l.append(list(map(int, input().split(' '))))
 
# dp할 배열 만들기
success = [[None for i in range(b)] for j in range(a)]
# success 내 값을 사용해서 종점을 미리 표시
success[-1][-1] = 1
 
 
def s(i, j):
    # 첫번쨰 탐색이고, 종점이 아닐때
    if success[i][j] is None and not (i == a - 1 and j == b - 1):
        success[i][j] = 0
 
        # 상하좌우 탐색
        if j < b - 1 and l[i][j] > l[i][j + 1]:
            # 탐색
            s(i, j + 1)
            # 한 뒤에 저장된 결과값을 지금에 더함
            success[i][j] += success[i][j + 1]
        if i < a - 1 and l[i][j] > l[i + 1][j]:
            s(i + 1, j)
            success[i][j] += success[i + 1][j]
        if i > 0 and l[i][j] > l[i - 1][j]:
            s(i - 1, j)
            success[i][j] += success[i - 1][j]
        if j > 0 and l[i][j] > l[i][j - 1]:
            s(i, j - 1)
            success[i][j] += success[i][j - 1]
 
 
s(0, 0)
print(success[0][0])