leah

Input

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다.

이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

1
2
3
4
5
6

from collections import deque
import sys
input = sys.stdin.readline

m, n = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(m)]

DP + DFS

처음에 시도했던 방법은 BFS + 스택 을 이용했다. 답은 나오는데 시간 초과가 떠서 실패했음. 생각해보니 스택을 쓰면 끝까지 가서 아닌 경우를 계속 체크하는 바람에 시간이 초과될 수밖에 없겠더라. 코드는 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def bfs(cnt):
  s = deque()
  s.append((0,0))

  while s:
    dx, dy = s.pop()

    for d in dir:
      x = dx + d[0]
      y = dy + d[1]

      if x == m-1 and y == n-1:
        cnt += 1
        break

      if 0 <= x < m and 0 <= y < n:
        if board[x][y] < board[dx][dy]:
          s.append((x, y))

  return cnt

print(bfs(0))

그리고 가만 보면 DFS만으로 해결할 수 있겠다 싶은 문제이지만, 시작점과 도착점이 고정되어 있는 상태에서 경우의 수를 체크하는 문제이기 때문에 DP 로 접근해야 한다. 근데 계속 트리 가지를 쳐가며 들어가는 문제이기 때문에 DFS 까지 결합됨.

조건을 살펴보면,

• 상하좌우로만 이동 가능

• 현재 지점보다 높이가 낮아야

일단 DFS이기 때문에 재귀 호출 한계를 설정해주고, DP로 각 DFS 시점의 방문지점을 체크하는 배열인 동시에 시작점에 도달했을 시 count++를 해주는 배열을 생성한다. 이 때, (0,0)에 도달했을 때만 count++를 해주어야 하므로 dp를 -1로 초기화하고, 방문하면 0으로 설정하여 dfs를 해나감에 있어서 count에 영향이 없도록 한다.

1
2
3
4
5
6
7
8

sys.setrecursionlimit(100000)

# dp: 각 경우의 visited + count 동시에 역할
# (0,0)에 도달했을 때만 cnt+1 되어야 하므로 -1으로 초기화하고,
# 방문 체크용으로는 0으로 해야 +에 지장이 없음.
dp = [[-1]*n for _ in range(m)]

dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]

그리고 DFS를 정의해준다.

• (0, 0)에 도달하면 count++: return 1

  1 2 3 4 5

  # 도착점 fix된 경우: parameter로 도착점 설정 def dfs(x, y): # 시작점 fix된 경우: return 경우 설정 if x == 0 and y == 0: return 1

• 처음 방문한 경우 dp를 0으로 세팅 (답이 존재하든 아니든 일단 방문했으므로 0으로 세팅해야 함) 하고, 상하좌우 이동 시 범위 내에 해당하면서 조건을 만족한다면 지금의 경로를 도착점 dp에 저장한다.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  # 방문 전 if dp[x][y] == -1: # 답이 있건 없건 방문 체크해야 함 dp[x][y] = 0 for d in dir: nx = x + d[0] ny = y + d[1] if 0 <= nx < m and 0 <= ny < n: # 목표 지점(현재 지점)보다 방문할 곳이 큰 경우 = 조건 if s[x][y] < s[nx][ny]: ### 전체 경로 (경우의 수) 체크 가능 dp[x][y] += dfs(nx, ny)

Output

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

• 결국 모든 경로의 수가 저장된 것은 dp[x][y] 이므로 이를 출력한다.

1

return dp[x][y]

1

print(dfs(m-1, n-1))

Input

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)

1
2
3
4
5
6
7
8
9
10
11

import sys
input = sys.stdin.readline

n = int(input())
T = []
P = []
dp = [0]*(n+1)
for _ in range(n):
  t, p = map(int, input().split())
  T.append(t)
  P.append(p)

퇴사1 문제의 코드는 시간 초과가 떴는데, 차이는 빌트인 input 대신 sys.stdin.readline 을 썼다는 점이다.

DP

처음부터 시작하는 방식으로 문제를 풀어봤으나, 당연히 스킵해도 될 만한 케이스까지 체크하고 있었다. 이전에 퇴사1 문제에서 뒤에서부터 접근하며 문제를 풀었던 기억이 있어, 뒤에서부터 시작하는 방식으로 문제를 풀어나가니 필요없는 과정은 스킵하고 비교해야 할 대상만 비교하고 있었다. 그래서 뒤에서부터 접근하는 방식을 토대로 문제를 풀어봄.

1
2

# 최대값을 구하기 위해 기존 dp 값과 대상값 비교
for i in range(n-1, -1, -1):

일단 기본적으로, 연속적으로 답을 구해나가는 게 아니라 기존의 값보다 큰 값이 존재할 경우 대체해야 하는 최대값 구하기 문제이기 때문에,

• max를 사용하여 기존의 dp 값 과 이전 값 + 현재 값 을 비교해서 큰 값을 dp 에 저장

해야 한다는 것만 대강 잡고 문제를 풀어나갔다.

주어진 조건이

• 퇴사 이후에는 일을 할 수 없음

이기 때문에, i + T[i] > n 일 경우에는 P를 계산하는 과정이 스킵된다. 난 조건을 만족하는 경우에만 체크하는 if문을 작성하고 dp를 애초에 0으로 초기화해서, else로 예외처리를 안 해도 된다고 착각했는데 if를 사용할 때는 꼭 else 조건도 생각해보자! 해당 범위를 벗어나는 경우에는 P는 계산하지 않지만 이전의 dp 값을 받아와야 한다. 즉, 0으로 무조건 초기화하면 안 되고 dp를 가져와야 한다는 것… 주어진 예시에서는 퇴사 직전에만 일자를 벗어나지만 중간에 범위를 벗어나는 경우에는 0으로 초기화하면 dp 값을 제대로 전달하지 못한다. 반례로

1
2
3
4
5
6
7
8
9
10

"""
7
3 10
5 20
1 10
5 20
2 15
4 40
2 200
"""

위의 경우에서 T[3]은 5이기 때문에 퇴사 일자를 넘어서는데, dp[3]에 0을 저장하면 정상적으로 코드가 작동하지 않을 것임.

1
2

else:
  dp[i] = dp[i+1]

• 퇴사 전에 일이 해결될 경우,

  • 마지막 날이라면 P를 그대로 받아오고 (dp를 0으로 초기화해서 생성했기 때문에)

  • 그 외에는

    1. 해당 일자의 일을 스킵할 경우
    2. 해당 일자의 일을 받아들일 경우

    위 2가지 경우 중 max 값을 취하면 된다.

1
2
3
4
5
6

# 퇴사 전까지만
if i + T[i] <= n:
  if i == n-1:
    dp[i] = P[i]
  else:
    dp[i] = max(dp[i+1], dp[i + T[i]] + P[i])

Output

1

print(dp[0])

Input

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

1
2
3
4
5
6

import sys
input = sys.stdin.readline

n = int(input())
A = [1000]*1000
A[:n] = map(int, input().split())

DP

비슷한 문제를 풀어봤던 기억이 있어서, 그 방법대로 접근하려 했지만 문제를 풀어보니 내가 그 방식으로 풀고 있지 않았다.

원래는 체크하고 있는 값보다 큰 값의 index를 dp에 저장하고 n-1부터 시작해서 dp에 저장된 index를 연속적으로 방문하며 cnt+1 해나가는 방식을 썼던 것 같은데,

이번 문제는 index를 저장하는 것이 아닌, 체크하는 index 기준 긴 수열의 길이를 max로 비교하며 dp에 저장해나가고, 최종적으로 가장 큰 값을 출력하면 됐다.

예시를 풀어보면 다음과 같이 되는데,

1
2
3
4

"""
A   = [10, 30, 10, 20, 20, 10]
dp  = [ 1,  1,  2,  2,  2,  3]
"""

여기서 히든 케이스는 max 를 이용해 기존에 저장된 길이와 비교하여 큰 값으로 대체해야 한다는 점이다.

히든 케이스를 예시로 들어보면,

1
2
3
4

"""
A   = [10, 40, 30, 40, 10, 20, 20, 10]
dp  = [ 1,  1,  2,  1,  3,  3,  3,  4]
"""

푸는 방식을 일반화 해보니, 앞에서부터 체크해나가되 dp 값을 저장하기 위해서는 해당 index로부터 뒤로 가고 있더라. 코드로 짜보면 다음과 같다.

1
2
3
4

for a in range(1, n):
  for b in range(a-1, -1, -1):
    if A[b] > A[a]:
      dp[a] = max(dp[a], dp[b] + 1)

전 값과 비교하면서

• 전 값이 클 경우, 기존 dp[a] 에 저장된 길이와 dp[b] 를 비교해 max 값을 저장한다.
• 여기서 끝내지 않고 index=0까지 방문하기 때문에 최외곽 index 기준으로 가장 긴 수열의 길이를 저장하게 된다.

Output

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

1

print(max(dp))

IndexError로 인한 런타임 에러를 방지하기 위해 최대 길이의 배열을 생성했으므로… dp[n-1] 이 아닌 max 를 이용해 가장 큰 값에 접근해야 한다.

Input

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

1
2
3
4

import sys
input = sys.stdin.readline

n = int(input())

DP

처음 접근했던 방식은 다음과 같다.

나름 찾았던 조건과 규칙성이,

• 가로 막대를 놓으면 밑에도 가로여야 하며, 얘네는 마치 세로 막대가 2개 묶인 것처럼 취급한다. 따라서, 세로 막대 개수를 n - i 인 것처럼 생각한다.
• 전체 n - i 개의 막대 중에서 i 개의 가로 막대를 고른다. 즉, 조합처럼 생각해서 (n-i)C(i) 를 cnt에 더한다.

그래서 다음과 같이 코드를 짰다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

ava = n // 2

def factorial(i):
  if i < 2:
    return 1
  
  return i * factorial(i-1)

# 가로 막대 i개
for i in range(ava+1):
  if i == 0:
    cnt += 1
  elif n - i < i:
    cnt += 1
  else:
    div = 1
    for k in range(i):
      div *= (n - i - k)
    cnt += div / factorial(i)

근데 틀림.

답은 간단하다.

n을 1부터 체크해나가면 다음과 같은 규칙성을 보인다.

1
2
3
4
5
6
7

"""
n = 1 -> cnt = 1
n = 2 -> cnt = 2
n = 3 -> cnt = 3
n = 4 -> cnt = 1+1+3 = 2+3 = 5
n = 5 -> cnt = 1+4+3 = 5+3 = 8
"""

따라서, 점화식은 다음과 같다.

1

점화식: cnt[i] = cnt[i-1] + cnt[i-2]

이걸 그대로 코딩하면 된다.

1
2
3

cnt = [0, 1, 2]
for i in range(3, n+1):
  cnt.append(cnt[i-2]+cnt[i-1])

여기서 덧붙이면, DP는 배열을 사용하기 때문에 index out of list Error가 잘 날 수 있다.

따라서, 그냥 배열 크기를 문제에 주어진 최대 범위로 설정해놓자.

Output

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

1

print(cnt[n] % 10007)

Input

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

1
2
3
4
5
6
7
8

import sys
input = sys.stdin.readline

n = int(input())
score = [0]*301
for i in range(n):
  score[i] = int(input())
dp = [0]*301

배열을 생성할 때 웬만하면 백준에서 주는 최대값을 크기로 해주는게 좋다. 생각보다 IndexError 런타임 에러가 많이 나기 때문… 기본적인 경우로 코딩해놓고 히든케이스 때문에 index가 벗어날 수 있다.

DP

DP는 규칙을 찾고 코딩하다 내가 말리는 기분이다…

먼저 처음 접근 방식은 이랬음.

1
2
3
4
5
6
7
8

"""
규칙이 반복되는데 그 중 최대값 구하기 = DP
1. 연속적으로 1 / 2 계단만 오를 수 있음
2. 점수의 최대값

- 3개 이상 연속되지 않는 조합
- 그 중 최대값
"""

나름 규칙 찾고, 2중 중첩 반복문으로 케이스를 모두 비교해서 최대값을 찾아야 하나 싶었음. 나름 끝에서부터 접근하는 방식은 맞았다만, 문제는 시작점부터 어떤 계단을 밟을지 고르는 방법과 동일하게 도착점에서 어떤 계단을 밟고 왔나 고르는 방법으로 풀었다는 거다.

여기서 생각을 좀 틀어서, 처음부터 더해나가되 어떤 계단을 밟았는지 알고, 고를 수 있는 index부터 어떤 계단을 밟을지 골라야 한다는 거다. 결국 도착점에서 모든 케이스를 비교하는게 아니라, 올라가면서 전까지 밟아온 케이스를 비교하고 골라야 한다는 것.

그래서 먼저 가능한 케이스를 정의해둔다.

1
2
3

dp[0] = score[0]
dp[1] = dp[0] + score[1]
dp[2] = max(dp[0] + score[2], score[1] + score[2])

어, 첫번째 칸을 안 밟을 수도 있는데…! 라고 생각했지만 이후 규칙성을 반영해서 일반적인 케이스를 코딩하면 이미 3번째 계단에 있는 내가 첫번째를 안 밟는 케이스를 선택할 수도 있다.

이후 일반적인 케이스 코딩.

1
2

for i in range(3, n):
  dp[i] = max(dp[i-3] + score[i-1] + score[i], dp[i-2] + score[i])

결국 점화식은 다음과 같다.

1
2
3
4
5
6
7
8

# 현재 칸을 밟는다는 가정 하에,
# 이전 칸을 밟은 경우:
	# 전전 칸을 밟았으면 안 됨
	dp[i-3] + score[i-1] + score[i]
	
# 이전 칸을 밟지 않은 경우:
	# 전전 칸까지 밟을 수 있음
  dp[i-2] + score[i]

위 2가지 경우 중에 max 값을 골라 저장하면 된다.

Output

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

1

print(dp[n-1])

Input

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

1
2
3
4
5

import sys
input = sys.stdin.readline

for _ in range(int(input())):
  n = int(input())

굳이 t 변수를 생성하지 않아도 됨

Output

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

1

print(ret[n-1])

DP

가장 중요한 건, 규칙성을 파악하는 것이다.

DFS나 BFS와는 다르게 DP는 규칙성을 파악하는게 더 어려운 것 같다. 무조건 반복이 아니라 규칙에 따라 기존의 값을 활용해야 하기 때문인가…

이 문제도 규칙성을 파악하면 점화식을 만드는 건 하나도 어렵지 않음.

예를 들어n = 4 라고 한다면,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

"""
규칙
1 = 1
2 = 1+1
  = 2
3 = 1+1+1
  = 2+1
  = 1+2
  = 3
4 = 1+1+1+1 => 3 ++1
  = 2+1+1 => 3 ++1
  = 1+2+1 => 3 ++1
  = 1+1+2 => 2 ++2
  = 2+2 => 2 ++2
  = 3+1 => 3 ++1
  = 1+3 => 1 ++3
"""

결국 1,2,3으로 숫자를 만들어야 하니 1,2,3 자체만 default로 경우의 수를 배열에 세팅해놓은 다음 이를 토대로 4부터 조합을 찾아가면 된다.

4의 경우 3의 모든 경우에 +1씩 하면 되고 (4 = 3+1 이니,) 2에 +2씩, 1에 +3씩 하면 된다. 즉, 점화식은 다음과 같다.

1

ret[n] = ret[n-1] + ret[n-2] + ret[n-3]

코드는 다음과 같다.

1
2
3
4

ret = [1, 2, 4]

for i in range(3, n):
  ret.append(ret[i-1] + ret[i-2] + ret[i-3])

Input

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

1
2
3
4

import sys
input = sys.stdin.readline

n = int(input())

Output

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

1

print(dp[n])

DP

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

조건이 위와 같이 주어져 있는 상태에서,

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값 을 출력하시오.

최소 연산 횟수을 구하는 문제이니, DP 를 활용해야 한다.

DP를 위해 점화식 을 구해보면 다음과 같다. 조건 그대로 정리하면 매우 간단.

1

dp(N) = min(dp(N//3)+1, dp(N//2)+1 , dp(N-1)+1)

먼저

• default: 1을 뺀다, 즉, index가 1 증가하면 연산 횟수도 1 증가한다.
• x % 3 == 0 : 1을 빼는 경우 vs 3으로 나눈 몫의 연산 횟수 값에 1 증가시키기
• x % 2 == 0 : 1을 빼는 경우 vs 2으로 나눈 몫의 연산 횟수 값에 1 증가시키기

이 3가지를 모두 체크해봐야 하므로 모두 if 문으로 처리 (elif 가 아님)

1
2
3
4
5
6
7
8

for i in range(2, n+1):
  dp[i] = dp[i-1] + 1

  if i % 3 == 0:
    dp[i] = min(dp[i], dp[i // 3] + 1)

  if i % 2 == 0:
    dp[i] = min(dp[i], dp[i // 2] + 1)

구하고자 하는 n 까지 도달하면 dp[n] 에는 최소 연산 횟수가 담겨있을 것이므로 출력하면 됨.

Input

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

1
2
3
4

import sys
input = sys.stdin.readline

n = int(input())

Output

첫째 줄에 n번째 피보나치 수를 출력한다.

1

print(arr[-1])

DP

재귀로 풀면 안 된다. 시간 초과 남

DP로 배열 써서 풀어야 한다.

1
2
3
4

arr = [0, 1]

for i in range(2, n+1):
  arr.append(arr[i-2] + arr[i-1])

코드를 복사 붙여넣기 할 때는 조건을 잘 수정하자…

-이상 조건 하나 잘못 넣어서 삽질하는 바람에 시간 초과 뜬 인간이..

Input

첫째 줄에 정수 K가 주어진다.

둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다.

그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다.

W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.

1
2
3
4
5
6
7

from collections import deque
import sys
input = sys.stdin.readline

k = int(input())
w, h = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(h)]

Output

첫째 줄에 원숭이의 동작수의 최솟값을 출력한다.

시작점에서 도착점까지 갈 수 없는 경우엔 -1을 출력한다.

1
2
3
4

while q:
	if y == h-1 and x == w-1: return visited[y][x][z]

return -1

BFS

한 경우에 트리를 파고 들어가는 형식이라 DFS라고 생각했는데, BFS로 풀어야 했다.

이유는

• 동일한 시작점과 도착점을 가지는 와중에
• 방향에 따라 경우를 파서 들어가야 하기 때문이고,
• 모든 값을 저장하는 것이 아니라 먼저 조건을 만나는 경우에 출력하고 끝내기 때문이다.

이 문제의 조건은 다음과 같다.

1. k 번만 말과 같이 이동 가능
2. 이후에는 인접한 칸 (상하좌우) 이동 가능

과정은

• 시작점은 (0,0)으로 동일 & 도착점은 (w-1,h-1)으로 동일
• 가능한 모든 direction을 시도해봐야 함
• 하나의 경우가 끝나면 count append, visited 초기화

이래서 DFS를 시도했으나, BFS와 3차원 배열을 활용하고 킥 포인트로 최소값 == 가장 먼저 break point를 만나는 경우 를 체크하면 됐다.

그래서 위의 과정을 수정해보면,

• 시작점과 도착점이 동일한 상태에서 여러번의 경우의 수가 존재하므로 bfs를 이용한다!
• 3차원 배열을 생성하여 가능한 모든 좌표에 대하여 k의 경우의 수를 포함한다.
• 초기화 하는 것이 아닌, 최소값을 구하는 경우이므로 가장 먼저 break point를 만나는 경우를 출력하고 종료하면 됨.

먼저, 정해진 direction이 존재하니 이걸 배열에 저장해 놓고,

1
2
3

# [dy, dx]
horse = [[2, -1], [-2, 1], [-1, -2], [-1, 2], [2, -1], [2, 1], [1, -2], [1, 2]]
dir = [[-1, 0], [0, -1], [0, 1], [1, 0]]

bfs를 정의한다.

1
2
3
4

def bfs():
  q = deque()
  q.append((0,0,k))
  visited = [[[0]*31 for _ in range(w)] for _ in range(h)]

• 여기서! k가 0 이상 30 이하이므로 31번 만큼 visited 배열을 더해서 3차원 배열을 만든다. 즉, visited를 별도의 배열이 아니라 기존 board에 추가하는 것.

break point를 설정하고,

1
2
3
4
5

while q:
  y, x, z = q.popleft()

  # 가장 먼저 도착하는 경우가 최소 횟수
  if y == h-1 and x == w-1: return visited[y][x][z]

default direction을 수행한다.

1
2
3
4
5
6
7
8
9

# default direction 먼저 append 하고
for d in dir:
  dy, dx = d
  ny = y + dy
  nx = x + dx

  if 0 <= ny < h and 0 <= nx < w and board[ny][nx] != 1 and visited[ny][nx][z] == 0:
    visited[ny][nx][z] = visited[y][x][z] + 1
    q.append((ny, nx, z))

더하여, 말의 이동경로는 디폴트가 아니라 경우를 따져야 하므로 밑에 조건을 덧붙인다.

1
2
3
4
5
6
7
8
9
10
11

# k > 0 인 경우 따로 경우를 더한다.
if z > 0:
  for d in horse:
    dy, dx = d
    ny = y + dy
    nx = x + dx

    ### 복붙할 때는 조건을 완벽히 확인하자...
    if 0 <= ny < h and 0 <= nx < w and board[ny][nx] != 1 and visited[ny][nx][z-1] == 0:
      visited[ny][nx][z-1] = visited[y][x][z] + 1
      q.append((ny, nx, z-1))      

큐에서 break point를 만나지 못한 상태로 break 되면, 경우의 수가 존재하지 않는 것이므로 조건에 따라 -1을 출력한다.

1

return -1

Input

첫째 줄에는 수열의 길이 N이 주어지고,

둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다.

N은 1 이상 100,000 이하의 정수이다.

1
2
3
4
5
6

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

N = int(input())
num = list(map(int, input().split()))

Output

첫째 줄에 가장 긴 길이를 출력한다.

1
2
3

if index == N-1:
  print(max(map(max, increment, decrement)))
  return

DP

체크해야 할 경우는 2가지인데,

1. 연속해서 증가하는 경우
2. 연속해서 감소하는 경우

위 2가지 중 더 긴 수열의 길이를 출력하면 된다.

따라서 default로 길이가 본인의 길이인 1로 초기화된 배열을 2개 생성하고,

1
2

increment = [1]*N
decrement = [1]*N

재귀함수를 정의한다.

• break point: index가 끝에 도달하면 max 값을 출력한다.

  1 2 3

  if index == N-1: print(max(map(max, increment, decrement))) return

• 연속해서 증가하는 경우: increment 배열에 그 전까지의 길이+1 를 append 한다.

  1 2	if num[index + 1] >= num[index]: increment[index+1] += increment[index]

• 연속해서 감소하는 경우: decrement 배열에 그 전까지의 길이+1 를 append 한다.

  1 2	if num[index + 1] <= num[index]: decrement[index+1] += decrement[index]

• 진행하기 위해서 재귀 함수를 호출한다.

  1	return lengthen(index+1)

• 첫 시작을 위해서,

  1	lengthen(0)