백준 2096. 내려가기

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

2096번: 내려가기

이 문제를 풀면서 메모리에 대해서 다시 한번 생각해보게 됐다.

일단 처음에 이 문제를 풀때 100001 x 3 크기의 int 형 배열 두개를 만들어서 풀었다. 

문제에서 최대 메모리가 4MB이고, 100001 x 3 크기의 int형 배열 하나가 약 120만 바이트 = 1.2MB이므로 충분할것으로 생각했다.

근데 풀면서 느낀게 골드4 문젠데 너무쉽고, 메모리가 단 4MB만 주어진걸 봐서 뭔가 틀린것 같긴 했고 결국 메모리 초과를 받았다.

 

내가 생각하기에 내가 쓴 메모리는 대략 2 ~ 3MB인데 왜 메모리 초과가 날까? 

PS 문제 메모리 초과 이유: (https://tose33.tistory.com/580)

​ 

해결한 방법은 입력값을 저장할 100001 x 3의 배열 한개와, 최대 최소 값을 갱신할 2x3 크기의 배열 한개로 풀었다.

이 문제는 위에서 부터 내려가면서 현재 칸의 최대 혹은 최소값을 갱신해 나가는 것이고,

갱신하는 방법은 첫번째 칸은 위의 첫번째칸과 두번째 칸에서 부터 갈수 있으므로, 위의 첫번째 칸과 두번째 칸중 큰값에 현재 칸의 숫자를 더하는 것이다. 다른 칸도 마찬가지고, 최솟값은 작은 값을 고르면 된다.

 

d[i][j]는 (i,j)까지 왔을때의 최댓값 or 최솟값이라고 하면 점화식은 

d[i][0] = max(d[i-1][0] + a[i][0], d[i-1][1] + a[i][1])

d[i][1] = max(d[i-1][0] + a[i][1], d[i-1][1] + a[i][1], d[i-1][2] + a[i][1])

d[i][2] = max(d[i-1][1] + a[i][2], d[i-1][2] + a[i][2])

 

보통이라면 d도 input 값이 저장된 크기 만큼 만들어서 갱신해 나가면 되지만 이 문제는 메모리 초과의 위험이 있다.

해결할수 있는 방법은 d의 행의 크기를 2 만큼만 만드는 것이다.

i번쨰 행의 최대 혹은 최소 값을 구하는데 필요한건 i-1번째만 필요하므로 배열의 행의 크기가 2여도 풀수있다.

현재 내가 계산하는 행이 0행이면 1행에 이전행이 저장되어 있을 것이고, 

1행이면 0행에 이전 행이 저장되어 있을 것이다.