글 읽기 - 시간 초과 어디를 어떻게 개선해야 할까요??

(追記) (追記ここまで)

시간 초과 어디를 어떻게 개선해야 할까요??

1208번 - 부분수열의 합 2

pengkakao 1년 전 0

비트마스킹 + map 을 통해서 구현했습니다. (Meet in the Middle 알고리즘 사용)

1% 에서 시간초과로 실패하는데 어느 부분을 어떻게 개선해야 할지 모르겠습니다..

주요 로직을 설명드리면
첫번째 부분 수열에 대해 각 수열들의 합계를 구한 후 저장할 때는 map에다가 저장하도록 해주었고
두번째 부분 수열에 대해서는 각 합계를 S 값과 비교하여 result에다가 바로 덧셈을 처리하도록 해주었습니다.

어떻게 개선해야 할까요??

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, S, arr[42], result = 0;
map<ll, ll> mp1, mp2;
void go(int init, int cond, map<ll, ll> &mp) {
	for(int i = 1; i < (1 << cond); ++i) {
		ll tmp = 0;
		for(int j = 0; j < cond; ++j) {
			if(i & (1 << j)) tmp += arr[init + j];
		}
		if (init != 0) {
			if(S == tmp) ++mp[tmp];
			if(tmp == 0) result += mp1[S];
			else if(tmp > 0) result += mp1[S - tmp];
			else if(tmp < 0) result += mp1[abs(tmp) + S];
		}
		else ++mp[tmp];
	}
}
int main() {
	cin.tie(0); ios::sync_with_stdio(NULL);
	cin >> N >> S;
	for(int i = 0; i < N; ++i) cin >> arr[i];
	go(0, N / 2, mp1);
	go(N / 2, N - N / 2 , mp2);
	cout << result + mp1[S] + mp2[S];
}

pengkakao 1년 전 0

왜인지는 자세히 알 수 없으나 .. map 2개를 1개로 줄여서 사용하니까 되네요.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, S, arr[42], result = 0, z = 0;
map<ll, ll> mp;
void go(int init, int cond) {
	for (int i = 1; i < (1 << cond); ++i) {
		ll tmp = 0;
		for (int j = 0; j < cond; ++j) {
			if (i & (1 << j)) tmp += arr[init + j];
		}
		if (init != 0) {
			if (S == tmp) ++z;
			if (tmp == 0) result += mp[S];
			else if (tmp > 0) result += mp[S - tmp];
			else if (tmp < 0) result += mp[abs(tmp) + S];
		}
		else ++mp[tmp];
	}
}
int main() {
	cin.tie(0); ios::sync_with_stdio(NULL);
	cin >> N >> S;
	for (int i = 0; i < N; ++i) cin >> arr[i];
	go(0, N / 2);
	go(N / 2, N - N / 2);
	cout << result + mp[S] + z << "\n";
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

시간 초과 어디를 어떻게 개선해야 할까요??

pengkakao 1년 전 0

pengkakao 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말