[다이내믹]-내려가기-백준-2096번
자원 제약
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 4 MB (하단 참고) | 60,722 | 23,501 | 18,460 | 36.863% |
문제
N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.
먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.
| * | ||
| O | O | X |
| * | ||
| O | O | O |
| * | ||
| X | O | O |
별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.
입력
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.
출력
첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.
예제 입력 1
3
1 2 3
4 5 6
4 9 0
예제 출력 1
18 6
예제 입력 2
3
0 0 0
0 0 0
0 0 0
예제 출력 2
0 0
풀이
문제에 주어진 그림을 통해서 abs(k - j) <= 1 이라는 이동 규칙을 찾아내는 것이 가장 어렵다.
일단 되는 것과 안 되는 것을 비교해 보자. 안 되는 것부터 확인하는 것이 문제의 성패를 가른다. 실패 케이스부터 보자.
안 되는 것
abs(0 - 2) == 2
abs(2 - 0) == 2
되는 것
abs(0 - 0) == 0
abs(0 - 1) == 1
abs(2 - 2) == 0
abs(2 - 1) == 1
abs(1 - 2) == 1
abs(1 - 1) == 0
abs(1 - 0) == 1
되는 것은 모두 절댓값이 1 이하이다.
물론 조건 상 abs(k - j) >= -1 and abs(k - j) && 1도 상관없으나 코드 상 절댓값이 더 짧고, 어차피 음수로나 양수로나 0을 기점으로 대칭적으로 비교 범위가 있으니 그냥 절댓값 씌우자.
이 문제의 N을 보면 최대 100000이고, 파이썬에선 최소 한 자릿수 숫자당 28바이트 이상을 쓴다.
1.정수 객체 소모량: 300,000(개)×28(bytes)=8,400,000(bytes)
2.리스트 내 포인터 소모량: 300,000(개)×8(bytes)=2,400,000(bytes)
3.행 리스트 객체 오버헤드: 100,000(행)×64(bytes)=6,400,000(bytes)
4.리스트 1세트 합계 (1+2+3): 17,200,000(bytes)≈16.4(MiB)
5.전체 리스트 3세트 (board, max, min): 17,200,000×3=51,600,000(bytes)≈49.2(MiB)
6.최종 합산 (5 + 파이썬 런타임 및 입력 버퍼): 51.6(MB)+7.5(MB)=59.1(MB)≈59,144(KB)
틀린 코드
def find_max_scores_via_dp(board):
startpoint = len(board) - 1
for i in range(startpoint, 0, -1): # must reach i=1 to update row 0
prev_row = board[i-1][:] # snapshot to avoid in-place contamination
next_row = board[i] # row below (already dp-ed)
for k in range(3):
best = -10**18
for j in range(3):
if abs(k - j) <= 1: # should find move rules from a picture
best = max(best, prev_row[k] + next_row[j])
board[i-1][k] = best
return max(board[0])
def find_min_scores_via_dp(board):
startpoint = len(board) - 1
for i in range(startpoint, 0, -1): # must reach i=1 to update row 0
prev_row = board[i-1][:] # snapshot to avoid in-place contamination
next_row = board[i]
for k in range(3):
best = 10**18
for j in range(3):
if abs(k - j) <= 1:
best = min(best, prev_row[k] + next_row[j])
board[i-1][k] = best
return min(board[0])
def main():
board = []
rows = int(input())
for _ in range(rows):
a, b, c = map(int, input().split())
board.append([a, b, c])
# max/min must not share the same mutated board
board_for_max = [row[:] for row in board]
board_for_min = [row[:] for row in board]
print(find_max_scores_via_dp(board_for_max), end=" ")
print(find_min_scores_via_dp(board_for_min), end="")
main()
나름 DP 배열이 더러워지지 않게 하기 위한 안전장치도 넣었음에도 실패하였다.
yjlee@elegant:~/2096$ /usr/bin/time -v python3 wrong.py < input.txt
668205 231458 Command being timed: "python3 wrong.py"
User time (seconds): 0.25
System time (seconds): 0.03
Percent of CPU this job got: 98%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.28
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 59144
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 13336
Voluntary context switches: 1
Involuntary context switches: 19
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
실제로 확인된 결과를 보면 문제의 조건인 4MB에서 파이썬 특혜로 10MB정도 줘도 PS용으론 턱없이 모자람을 알 수 있다.
여기서 우리는 영리하게 접근해야 한다.
당장의 DP를 위해서 우리가 필요한 것은 모든 것이 합류할 첫 줄의 상태와 대상이 될 줄의 상태이다.
이것을 유지하기 위해서 구조를 냉정히 쪼개 보자.
- 첫번째 줄을 받는다.
- 다음 줄을 받아서 최대를 찾아서, 둘째 줄과 더할 시 최대, 최소가 되는 수만 min이나 max로 집어서 각각의 DP배열에 집어넣는다.
- 업데이트된 DP배열에 세번째 줄이 들어와도 최대와 최소가 갱신된다.
- 끝줄까지 반복한다.
이러면 결과적으로 이 DP는 가장 큰 값과 가장 작은 값만 가지게 된다.
맞힌 코드
import sys
def main():
input = sys.stdin.readline
n = int(input().strip())
row = list(map(int, input().split()))
max_dp = row[:]
min_dp = row[:]
for _ in range(n - 1):
row = list(map(int, input().split()))
prev_max = max_dp
prev_min = min_dp
max_dp = [0, 0, 0]
min_dp = [0, 0, 0]
for k in range(3):
best_max = -10**18
best_min = 10**18
for j in range(3):
if abs(k - j) <= 1:
best_max = max(best_max, prev_max[j])
best_min = min(best_min, prev_min[j])
max_dp[k] = row[k] + best_max
min_dp[k] = row[k] + best_min
print(max(max_dp), min(min_dp))
if __name__ == "__main__":
main()
-(10^18)이나 10^18은 극단적인 값이기 때문에 문제의 입력 범위 안에서는 항상 저 값으로 떨어지지 않기 때문에 min, max를 저장하기 위한 변수들을 그러한 값으로 설정한다.
이렇게 한 줄씩 고려하고 계산하면 9개의 수 안에서 4개 정도의 추가 정수만 사용해서 게임이 끝난 후의 값을 가지게 된다. 보드의 끝에서 단순히 최대 최소를 찾아도 3개 뿐이므로 연산 비용이 낮다. 그러니 min, max만 걸면 된다.
이렇게 해서 /usr/bin/time으로 다시 재 보자.
Command being timed: "python3 right.py"
User time (seconds): 0.12
System time (seconds): 0.00
Percent of CPU this job got: 100%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.12
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 9488
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 925
Voluntary context switches: 1
Involuntary context switches: 4
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
메모리 사용량이 9.4MB로 급감했다. 이 정도면 웬만한 PS사이트에선 통과한다.
풀이에 대해 생각해 볼 것
N이 큰 DP문제 중 게임판이나 지도가 제시되는 것은 탐색과 헷갈리기 좋다. 이러한 것의 규칙을 찾아내는 것 역시 쉽지 않다.
이러한 문제를 잘 찾아내기 위해서는 반복적으로 푸는 것 이상의 문제 해체가 필요하다. 다음에는 이 문제를 해체 및 재조립해서, 3개가 아닌 5개를 위해 탐색하는 문제를 만들어 풀어 보도록 하겠다.