글 읽기 - 삼각 그래프 시간초과 + memset질문.

bsdlcksdn 8년 전 0

cache를 이용해서 걸러냈다고 생각했는데

25%까지 맞구, 시간초과가 나네요;;;

어디서 오류가 나는지 알 수 있을까요?

+ 그리구, cache배열을 초기화 하는 과정에서

cache[100010][3]배열을

memset(cache, INF, sizeof(cache))와 같이 해줬더니 이상한 값이나오네요..

그래서 배열로 돌렸더니 제대로 들어가구요..

memset을 위와 같이 사용하면 안될까요?

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 5000;

int board[100010][3];
int cache[100010][3];
int n, testcase;


int recur(int i, int j) {

	if (i == 0 && j == 1) {
		return board[i][j];
	}
	else if(i==0 && j==0){
		return INF;
	}

	if (cache[i][j] == INF) {

		if (j == 2) {
			
			if (i - 1 >= 0) {
				cache[i][j] = min(cache[i][j], board[i][j] + recur(i - 1, j));
				cache[i][j] = min(cache[i][j], board[i][j] + recur(i - 1, j - 1));
			}
			cache[i][j] = min(cache[i][j], board[i][j] + recur(i, j - 1));
		}

		else if (j == 1) {

			if (i - 1 >= 0) {
				cache[i][j] = min(cache[i][j], board[i][j] + recur(i - 1, j + 1));
				cache[i][j] = min(cache[i][j], board[i][j] + recur(i - 1, j));
				cache[i][j] = min(cache[i][j], board[i][j] + recur(i - 1, j - 1));
			}
			cache[i][j] = min(cache[i][j], board[i][j] + recur(i, j - 1));
		}

		else if (j == 0) {

			cache[i][j] = min(cache[i][j], board[i][j] + recur(i - 1, j));
			cache[i][j] = min(cache[i][j], board[i][j] + recur(i - 1, j + 1));
		}

	}
	
	return cache[i][j];
}


int main() {

	int testcase = 1;
	
	while (1) {
		cin >> n;

		if (n == 0) {
			return 0;
		}

		//cache초기화
		//memset(cache, INF, sizeof(cache));

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 3; j++) {
				cache[i][j] = INF;
			}

			cin >> board[i][0] >> board[i][1] >> board[i][2];
		}

		
		cout<<testcase++<<". "<<recur(n-1, 1)<<endl;
	}


}

joonas 8년 전 1

네. 비트단위 초기화를 하기 때문입니다. 자세한 이유는 https://www.acmicpc.net/board/view/6370#comment-13 에서 koosaga님이 잘 적어주셨어요.

bsdlcksdn 8년 전 1

아~.. 그래서 memset이 오류난거였군요... 감사합니다~

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

문제

문제

출처

ICPC

삼각 그래프 시간초과 + memset질문.

bsdlcksdn 8년 전 0

joonas 8년 전 1

bsdlcksdn 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말