백준 알고리즘 풀이 2096번 - 내려가기

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

2096번: 내려가기

2096번

---

- 다이내믹 프로그래밍 문제

 

알고리즘

---

현재 칸이 가장 왼쪽 위치인 경우 -> dp [1][0]=max(dp [0][0],dp[0][1])+ map[0]

현재 칸이 중간 위치인 경우 -> dp[1][1] = max(dp[0][0],dp[0][1],dp[0][2])+map[1]

현재 칸이 가장 오른쪽 위치 ->  dp[1][2] = max(dp[0][1],dp[0][2])+map[2]

 

시간 복잡도

---

총 n번(n<100001)만큼 입력받으므로, O(N) = n

각 줄마다 3개의 칸이 있고, 옮겨주는게 3번 진행, 가장 큰 거리와 가장 작은 거리를 구한다.

따라서 한 번 돌때마다 12번을 계산함을 알 수 있다. 

따라서 O(N) = n.

 

예외 조건

---

가장 긴 거리와 가장 짧은 길이를 구해야 하므로 길이를 저장할 배열을 두 개 생성해야 한다.

각 배열을 만들 때 경로를 다 저장하도록 만들기 쉬운데, 메모리 제한이 4mb여서 메모리 초과가 난다. 잘 생각해보면 우리가 필요한 정보는 바로 직전 칸과, 현재 칸의 최소/최대 길이임을 알 수 있다.

따라서 이전 칸들의 정보를 다 저장하지말고, 3X2배열을 2개 만들어서 바로 직전칸과 현재칸의 정보만 저장하도록 한다.

 

소스코드

---

#include <iostream>
#include <algorithm>

using namespace std;

int bigDp[2][4];
int smallDp[2][4];

int main()
{
	int num;
	cin>>num;
	for(int i=1;i<=num;i++){
		int a,b,c;
		cin>>a>>b>>c;
		bigDp[1][1]=max(bigDp[0][1],bigDp[0][2])+a;
		bigDp[1][2]=max(max(bigDp[0][1],bigDp[0][2]),bigDp[0][3])+b;
		bigDp[1][3]=max(bigDp[0][2],bigDp[0][3])+c;
		
		smallDp[1][1]=min(smallDp[0][1],smallDp[0][2])+a;
		smallDp[1][2]=min(smallDp[0][1],min(smallDp[0][2],smallDp[0][3]))+b;
		smallDp[1][3]=min(smallDp[0][2],smallDp[0][3])+c;
		for(int i=1;i<=3;i++){
			smallDp[0][i]=smallDp[1][i];
			bigDp[0][i]=bigDp[1][i];
		}
		
	}
	cout<<max(bigDp[0][1],max(bigDp[0][2],bigDp[0][3]))<<" "<<min(smallDp[0][1],min(smallDp[0][2],smallDp[0][3]));
}

 

 

틀린 내용이나 지적 언제나 환영입니다.

도움이 되었다면 하트 한 번씩 눌러주세요:)