2096번 내려가기 G4
N줄에 각 줄마다 0~9 인 숫자가 3개씩 적혀있고
첫 줄부터 시작해서 마지막 줄까지 내려가면 끝나는 놀이이다.
한 줄씩 내려갈 때 마다 숫자를 하나씩 골라서 내려가는데,
다음 줄로 내려갈 때는 고른 위치에 인접한 곳으로만 내려갈 수 있다.
바로 아래 칸이나 아래 칸에 붙어있는 칸으로만 갈 수 있다는 말이다.
이때 얻을 수 있는 최대 점수와 최소 점수를 구해야한다.
당연히 dp 문제이고 비슷한 문제를 풀어봐서 별로 고민하지 않았다.
근데 그냥 하던대로 하고나서 제출하기 전에 보니 메모리 제한이 4MB였고
그냥 그대로 내면 무조건 메모리 초과가 뜨는 코드였다.
그래서 숫자를 3개씩 입력 받으면서 dp 테이블도 함께 초기화 시킬 수 있도록 코드를 변경했다.
입력과 dp 테이블이 차지하는 공간은 n이 몇이어도 항상 똑같다.
내용은 단순하다.
dp[0]에는 최대값을, dp[1]에는 최소값을 저장했다.
한 줄 내려갈 때마다 이전 줄에서 최대값 혹은 최소값을 가져오면서 함께 더해주면
해당 칸으로 내려올 수 있는 최대, 최소 값이 된다.
3번째 줄 가운데 칸이라면
2번째 줄 왼쪽 위, 바로 위, 오른쪽 위 중에서 가장 큰 숫자를 가지고 와서 3번째 줄 가운데 숫자와 더하면
3번째 줄 가운데 칸으로 올 수 있는 최대 값이다.
물론 이때 2번째 줄에서 선택된 최대 값 역시 2번째 줄까지 올 수 있는 최대 값이다.
코드가 별로 이쁘지는 않은데 그냥 뒀다.
from sys import stdin
n = int(stdin.readline())
dp = [[0 for i in range(3)] for j in range(2)]
for i in range(n):
nums = list(map(int, stdin.readline().rstrip().split()))
left_max = max(dp[0][0], dp[0][1])
right_max = max(dp[0][1], dp[0][2])
left_min = min(dp[1][0], dp[1][1])
right_min = min(dp[1][1], dp[1][2])
dp[0][0] = nums[0] + left_max
dp[0][1] = nums[1] + max(left_max, right_max)
dp[0][2] = nums[2] + right_max
dp[1][0] = nums[0] + left_min
dp[1][1] = nums[1] + min(left_min, right_min)
dp[1][2] = nums[2] + right_min
print(str(max(dp[0]))+' '+str(min(dp[1])))
아래는 메모리 조건을 보지 않고 작성한 코드
from sys import stdin
n = int(stdin.readline())
nums = [list(map(int, stdin.readline().split())) for i in range(n)]
dp = [[[0 for i in range(3)] for j in range(n)] for k in range(2)]
dp[0][0][0] = nums[0][0]
dp[0][0][1] = nums[0][1]
dp[0][0][2] = nums[0][2]
dp[1][0][0] = nums[0][0]
dp[1][0][1] = nums[0][1]
dp[1][0][2] = nums[0][2]
for i in range(1, n):
left_max = max(dp[0][i-1][0], dp[0][i-1][1])
right_max = max(dp[0][i-1][1], dp[0][i-1][2])
dp[0][i][0] = nums[i][0] + left_max
dp[0][i][1] = nums[i][1] + max(left_max, right_max)
dp[0][i][2] = nums[i][2] + right_max
left_min = min(dp[1][i-1][0], dp[1][i-1][1])
right_min = min(dp[1][i-1][1], dp[1][i-1][2])
dp[1][i][0] = nums[i][0] + left_min
dp[1][i][1] = nums[i][1] + min(left_min, right_min)
dp[1][i][2] = nums[i][2] + right_min
print(max(dp[0][-1]), end=' ')
print(min(dp[1][-1]))
Author And Source
이 문제에 관하여(2096번 내려가기 G4), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@be-kid/2096번-내려가기-G4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)