글 읽기 - 4883 삼각 그래프 질문합니다.

wlsqudgk12 8년 전 0

아무리 테스트케이스를 짜 봐도... 맞는거같은데 ㅋㅋㅋㅋㅋㅋㅋ ㅠㅠㅠ 왜 문제죠

음수 생각도 해보고, 오버플로우 생각도 해봤는데왜 미렁;미램ㅈ댜;뢪ㄷㅁ

//#define DEBUG 1
//#define RECURSIVE 1
#define MEMOIZATION 1
//#pragma warning(disable:4996)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <limits>
using namespace std;

enum Position { LEFT, MID, RIGHT };

#define MAX_SIZE 1000000


int graph[3][MAX_SIZE];
long long score[3][MAX_SIZE];

long long min(long long a, long long b) {
	return a < b ? a : b;
}


long long min(long long a, long long b, long long c) {
	return min(min(a, b), c);
}

long long min(long long a, long long b, long long c, long long d) {
	return min(min(a, b), min(c, d));
}

#ifdef RECURSIVE
long long getCost(int col, int row) {
	if (row == 0) {
		switch (col) {
		case LEFT: {
			return numeric_limits<long long>::max();
		}
				   break;
		case MID: {
			return graph[col][row];
		}
				  break;
		case RIGHT: {
			return graph[col][row] + graph[col - 1][row];
		}
					break;
		}
	}
	else {
		switch (col) {
		case LEFT: {
			return min(getCost(col, row - 1), getCost(col + 1, row - 1)) + graph[col][row];
		}
				   break;
		case MID: {
			return min(getCost(col - 1, row - 1), getCost(col, row - 1), getCost(col + 1, row - 1)) + graph[col][row];
		}
				  break;
		case RIGHT: {
			return min(getCost(col - 1, row - 1), getCost(col, row - 1)) + graph[col][row];
		}
					break;
		}
	}

	return 0;
}

#elif MEMOIZATION
long long getCost(int col, int row) {
	if (row == 0) {
		switch (col) {
		case LEFT: {
			return numeric_limits<int>::max();
		}
				   break;
		case MID: {
			return graph[col][row];
		}
				  break;
		case RIGHT: {
			return graph[col][row] + graph[col - 1][row];
		}
					break;
		}
	}
	else if (score[col][row]) {
		return score[col][row];
	}
	else {
		switch (col) {
		case LEFT: {
			score[col][row] = min(getCost(col, row - 1), getCost(col + 1, row - 1)) + graph[col][row];
		}
				   break;
		case MID: {
			score[col][row] = min(getCost(col - 1, row - 1), getCost(col, row - 1), getCost(col + 1, row - 1), getCost(col -1, row)) + graph[col][row];
		}
				  break;
		case RIGHT: {
			score[col][row] = min(getCost(col - 1, row - 1), getCost(col, row - 1), getCost(col -1, row)) + graph[col][row];
		}
					break;
		}
	}

	return score[col][row];
}

#endif


int main() {
	int lineNum;
	int count = 0;


	do {

		for (int i = 0; i < 3; i++) {
			memset(score[i], 0, 100000);
		}

		score[LEFT][0] = graph[LEFT][0];
		score[MID][0] = graph[MID][0];
		score[RIGHT][0] = graph[RIGHT][0];


		++count;
		scanf("%d", &lineNum);
		if (!lineNum) {
			break;
		}

		for (int i = 0; i < lineNum; ++i) {
			scanf("%d %d %d\n", &graph[LEFT][i], &graph[MID][i], &graph[RIGHT][i]);
		}


		cout << count << ". " << static_cast<unsigned long long>(getCost(MID, lineNum - 1)) << endl;

	} while (lineNum);

}