[C++] 백준 BOJ - 내려가기 (2096)

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

2096번: 내려가기

 

TIL

1) 풀면서 놓쳤던 점

놓쳤던건 아니고 나는 역으로 생각했다 잘못생각함..ㅎ

잊을때쯤 다시한번 풀어보자용

아래서 위로 파악해야되는데, 위에서 아래로 파악하려했음

주어진 테스트케이스는 다 만족해서 잘 구현한줄알고 제출했는데 틀려서 왜인가했더니 !! 질문 게시판에 나랑 똑같이 생각한 사람이 있었당 ㅎㅎ

위에서 아래로 dp하다보면 충돌하는 케이스 생기는 ..  하나씩 써보면 알았을텐데.. 침착하고 꼼꼼하게 푸는 습관을 들이자 !!

 

2) 이 문제를 통해 얻어갈 것 

공간 복잡도 관련, 문제에서 메모리 제한을 4MB로 매우 제한적이게 둠. but, 

int로 수십만개 배열을 선언해도 10MB 미만.
100만개 int = 4Bytes * 100만 = 400만 Bytes = 약 3.8MBytes

출처 : https://subbak2.com/23

[BOJ 백준] 내려가기(2096) C++, Java

 

정답 코드

#include <cstdio>
#include <algorithm>
#include<climits>
int N, a,b,c;
int dpMax[3], dpMin[3];
int m[3], M[3];
int main() {
	scanf("%d", &N);
	scanf("%d %d %d", &dpMax[0], &dpMax[1], &dpMax[2]);
	dpMin[0] = dpMax[0], dpMin[1] = dpMax[1], dpMin[2] = dpMax[2];
	for (int i = 1; i < N;i++) {
		scanf("%d %d %d", &a, &b, &c);
		M[0] = std::max(dpMax[0],dpMax[1]) + a;
		M[1] = std::max(std::max(dpMax[0], dpMax[1]),dpMax[2]) + b;
		M[2] = std::max(dpMax[2], dpMax[1]) + c;
		m[0] = std::min(dpMin[0], dpMin[1]) + a;
		m[1] = std::min(std::min(dpMin[0], dpMin[1]),dpMin[2]) + b;
		m[2] = std::min(dpMin[2], dpMin[1]) + c;
		dpMax[0] = M[0], dpMax[1] = M[1], dpMax[2] = M[2];
		dpMin[0] = m[0], dpMin[1] = m[1], dpMin[2] = m[2];
		// 테스트용 출력
		//printf("max\n");
		//printf("%d %d %d", dpMax[0], dpMax[1], dpMax[2]);
		//printf("\nmin\n");
		//printf("%d %d %d", dpMin[0], dpMin[1], dpMin[2]);
		//puts("");
	}

	printf("%d %d", std::max(std::max(dpMax[0], dpMax[1]), dpMax[2]), std::min(std::min(dpMin[0], dpMin[1]), dpMin[2]));
	return 0;
}