[백준 17498번] 폴짝 게임 (시간 초과) - 실패

문제 링크: www.acmicpc.net/problem/17498

17498번: 폴짝 게임

카테고리는 다이나믹 프로그래밍입니다.

 

아직 제가 다이나믹 프로그래밍에 대한 이해가 부족한 탓인지,

일단 제 생각대로 구현을 성공적으로 했는데,

시간 초과 오류에 걸려 버리네요.

 

검색해보니 다이나믹 프로그래밍 중,

계산한 값을 배열에 미리 담아 두는 '메모이제이션' 기법이 있다고 합니다.

 

내일 관련 내용을 공부한 후 처음부터 다시 도전해봐야겠습니다.

 

 

	#include <iostream>
	#include <vector>
	#include <cmath>
	//#include <time.h>
	#define MIN_VALUE -1e12
	using namespace std;
	int N, M, D;
	vector <vector <int > > v;
	vector <int> v2;
	long long score = 0;
	long long currentMax = MIN_VALUE; //현재의 최대값; 새 좌표 시작시마다 0으로 초기화됨
	int currentN = 0;
	int currentM = 0; //현재의 최댓값이 위치한 좌표
	int locationN = 0;
	int locationM = 0; //현재 위치한 좌표
	//시작행, 시작열, 도착행, 도착열
	bool isReachable(int startN, int startM, int endN, int endM) {
	if (startN > endN)
	return false;
	if (abs(endN-startN) + abs(endM-startM) <= D)
	return true;
	else
	return false;
	}
	void search(int startN, int startM, int goalN, int goalM) {
	if (isReachable(startN, startM, goalN, goalM) == false)
	return;
	int temp = v[startN][startM] * v[goalN][goalM];
	if (temp > currentMax) {
	currentMax = temp;
	currentN = goalN;
	currentM = goalM;
	}
	}
	void reset() {
	score += currentMax;
	currentMax = 0;
	locationN = currentN;
	locationM = currentM;
	currentN = 0;
	currentM = 0;
	}
	int main() {
	/*clock_t start,end;
	start = clock(); */
	ios_base::sync_with_stdio(false);
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
	v.push_back(v2);
	for (int j = 0; j < M; j++) {
	int input;
	cin >> input;
	v[i].push_back(input);
	}
	}
	for (int i = 0; i < M; i++) {
	for (int j = 1; j < N; j++) {
	for (int k = 0; k < M; k++) {
	search(locationN,i,j,k);
	}
	}
	}
	reset();
	while (locationN != N-1) {
	for (int i = locationN+1; i < N; i++) { //탐색 대상이 되는 N
	for (int j = 0; j < M; j++) { //탐색 대상이 되는 M
	search(locationN,locationM,i,j);
	}
	}
	reset();
	}
	cout << score;
	/*
	end = clock();
	double result = (double)(end-start);
	cout << '\n' << result << endl;
	*/
	return 0;
	}

view raw 17498_폴짝게임_실패.cpp hosted with ❤ by GitHub

	#include <iostream>
	#include <vector>
	#include <cmath>
	//#include <time.h>
	#define MIN_VALUE -1e12
	using namespace std;
	int N, M, D;
	vector <vector <int > > v;
	vector <int> v2;
	long long score = 0;
	long long currentMax = MIN_VALUE; //현재의 최대값; 새 좌표 시작시마다 0으로 초기화됨
	int currentN = 0;
	int currentM = 0; //현재의 최댓값이 위치한 좌표
	int locationN = 0;
	int locationM = 0; //현재 위치한 좌표
	//시작행, 시작열, 도착행, 도착열
	bool isReachable(int startN, int startM, int endN, int endM) {
	if (startN > endN)
	return false;
	if (abs(endN-startN) + abs(endM-startM) <= D)
	return true;
	else
	return false;
	}
	void search(int startN, int startM, int goalN, int goalM) {
	if (isReachable(startN, startM, goalN, goalM) == false)
	return;
	int temp = v[startN][startM] * v[goalN][goalM];
	if (temp > currentMax) {
	currentMax = temp;
	currentN = goalN;
	currentM = goalM;
	}
	}
	void reset() {
	score += currentMax;
	currentMax = 0;
	locationN = currentN;
	locationM = currentM;
	currentN = 0;
	currentM = 0;
	}
	int main() {
	/*clock_t start,end;
	start = clock(); */
	ios_base::sync_with_stdio(false);
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
	v.push_back(v2);
	for (int j = 0; j < M; j++) {
	int input;
	cin >> input;
	v[i].push_back(input);
	}
	}
	for (int i = 0; i < M; i++) {
	for (int j = 1; j < N; j++) {
	for (int k = 0; k < M; k++) {
	search(locationN,i,j,k);
	}
	}
	}
	reset();
	while (locationN != N-1) {
	for (int i = locationN+1; i < N; i++) { //탐색 대상이 되는 N
	for (int j = 0; j < M; j++) { //탐색 대상이 되는 M
	search(locationN,locationM,i,j);
	}
	}
	reset();
	}
	cout << score;
	/*
	end = clock();
	double result = (double)(end-start);
	cout << '\n' << result << endl;
	*/
	return 0;
	}

view raw main.cpp hosted with ❤ by GitHub

제 시도가 늘 정답일 순 없고,

접근 방법이 잘못되었다면 어떻게 접근했고 왜 잘못되었는지 파악하는 것도 중요하다고 생각하여

실패 답안을 남겨둡니다.