글 읽기 - 1248번 시간 줄이기

fbfbf1 3년 전 0

어떻게 하면 시간을 줄일 수 있을까요?

S[i][j]에서

i == j 일때의 부호가 숫자의 부호라는 걸 이용했고

재귀 함수를 돌 때 마다 okay함수를 이용해서

s[i][j]에 있는 걸 만족하는지 아닌 지를 체크해줬습니다.

또한 ====

밑에 있는 코드는 맞은 코드인데

위 아래 코드의 차이가 무엇인 지 알 수 있을까요

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

char board[11][11];
int N, num = 0, cnt = 0;
string s;
vector<int> v(21);
vector<char> number;
vector<int> result(11);
vector<vector<int>> ff;

void init() {
	for (int i = 0; i < 11; i++)
		for (int j = 0; j < 11; j++) board[i][j] = ' ';
	for (int i = 0; i <= 20; i++) v[i] = i - 10;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) if (i <= j)board[i][j] = s[num++];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i == j) number.push_back(board[i][j]);
		}
	}
}

bool okay(int idx) {
	for (int i = 0; i <= idx; i++) {
		int sum = 0;
		sum += result[i];
		for (int j = i + 1; j <= idx; j++) {
			sum += result[j];
			if (board[i][j] == '0') {
				if (sum != 0) return false;
			}

			else if (board[i][j] == '-') {
				if (sum >= 0) return false;
			}

			else if (board[i][j] == '+') {
				if (sum <= 0) return false;
			}

		}
	}
	return true;
}

void go(int idx) {
	if (idx == N) {
		if (!cnt) ff.push_back(result);
		cnt++;
		return;
	}
	if (number[idx] == '-') {
		for (int i = 0; i <= 9; i++) {
			result[idx] = v[i];
			if (!okay(idx)) continue;
			go(idx + 1);
		}
	}
	else if (number[idx] == '0') {
		result[idx] = 0;
		go(idx + 1);
	}
	else if (number[idx] == '+') {
		for (int i = 11; i <= 20; i++) {
			result[idx] = v[i];
			if (!okay(idx)) continue;
			go(idx + 1);
		}
	}
	return;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> s;
	init();
	go(0);
	for (int i = 0; i < N; i++) cout << ff[0][i] << " ";
}

=============================================
    
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

char board[11][11];
int N, num = 0, cnt = 0;
string s;
vector<int> v(21);
vector<char> number;
vector<int> result(11);

void init() {
	for (int i = 0; i < 11; i++)
		for (int j = 0; j < 11; j++) board[i][j] = ' ';
	for (int i = 0; i <= 20; i++) v[i] = i - 10;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) if (i <= j)board[i][j] = s[num++];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i == j) number.push_back(board[i][j]);
		}
	}
}

bool okay(int idx) {
	for (int i = 0; i <= idx; i++) {
		int sum = 0;
		sum += result[i];
		for (int j = i + 1; j <= idx; j++) {
			sum += result[j];
			if (board[i][j] == '0') {
				if (sum != 0) return false;
			}

			else if (board[i][j] == '-') {
				if (sum >= 0) return false;
			}

			else if (board[i][j] == '+') {
				if (sum <= 0) return false;
			}

		}
	}
	return true;
}

bool go(int idx) {
	if (idx == N) {
		return true;
	}
	if (number[idx] == '-') {
		for (int i = 0; i <= 9; i++) {
			result[idx] = v[i];
			if (okay(idx) && go(idx + 1)) return true;
		}
	}
	else if (number[idx] == '0') {
		result[idx] = 0;
		return okay(idx) && go(idx + 1);
	}
	else if (number[idx] == '+') {
		for (int i = 11; i <= 20; i++) {
			result[idx] = v[i];
			if (okay(idx) && go(idx + 1)) return true;
		}
	}
	return false;;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> s;
	init();
	go(0);
	for (int i = 0; i < N; i++) cout << result[i] << " ";
}

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

문제

문제

출처

ICPC

1248번 시간 줄이기

fbfbf1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말