글 읽기 - 사탕 잘 줍는 방법이 있나요?

rnjsxo33 7년 전 0

가로줄을 선택했을떄의 최대값을 먼저 각각 구한뒤,

최대값들을 다시 세로줄로 선택하는 방법을 실행했는데 시간초과가 납니다.

사탕을 어떻게 하면 더 빨리 주울수 있을까요?

#include <iostream>
#include <algorithm>
using namespace std;


int cache_temp[100002]; int cache_Sum[100002];/*
											  bool visit[10000] = { 0, };*/
int temp[100002];
int Sum[100002];
int M = 1, N;
int ans_row = 0;
int ans = 0;

int openFunc_row(int startIndex, int nowSum) {
	if (nowSum > cache_temp[startIndex]) {
		cache_temp[startIndex] = nowSum;
		if (startIndex + 2 < N)
			openFunc_row(startIndex + 2, nowSum + temp[startIndex + 2]);
		if (startIndex + 3 < N)
			openFunc_row(startIndex + 3, nowSum + temp[startIndex + 3]);
	}
	return 0;
}

int openFunc(int startIndex, int nowSum) {
	if (nowSum > cache_Sum[startIndex]) {
		cache_Sum[startIndex] = nowSum;
		if (startIndex + 2 < M)
			openFunc(startIndex + 2, nowSum + Sum[startIndex + 2]);
		if (startIndex + 3 < M)
			openFunc(startIndex + 3, nowSum + Sum[startIndex + 3]);
	}
	return 0;

}
int funcgo_row() {
	if (N >= 1)
		openFunc_row(0, temp[0]);
	if (N >= 2)
		openFunc_row(1, temp[1]);
	return 0;
}

int funcgo() {
	if (M >= 1)
		openFunc(0, Sum[0]);
	if (M >= 2)
		openFunc(1, Sum[1]);
	return 0;
}

int init() {
	ios::sync_with_stdio(false); // 속도 개선
	int tempSum, tempOdd, tempEven;
	bool tt = true;
	while (tt) {
		cin >> M >> N;

		if (M == 0 || N == 0) {
			tt = false;
			break;
		}
		for (int i = 0; i < M; ++i)
			cache_Sum[i] = 0;

		for (int i = 0; i < M; ++i) {

			for (int i = 0; i < N; ++i) {
				cache_temp[i] = 0;
			}

			for (int j = 0; j < N; ++j) {
				cin >> temp[j];
			}

			funcgo_row();
			Sum[i] = max(cache_temp[N-1], cache_temp[N-2]);
		}
		funcgo();
		cout << max(cache_Sum[M-1], cache_Sum[M-2])<< endl;

	}
	return 0;
}

int main() {
	init();
	funcgo();
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

사탕 잘 줍는 방법이 있나요?

rnjsxo33 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말