글 읽기 - 시간초과 질문드립니다.

dksdmssh1212 3년 전 0

dp[i][j] 2차원 디피로 해결하려고 했습니다.

예를 들어

i는 0부터 5의 값을 갖습니다.

i가 0일 때, 볼륨을 빼는 것만 가능하고,

1일 때는 더하는 것만 가능하고,

2일 때는 둘 다 불가능 하고

3, 4일 때는 더하는 것과 빼는 것 둘 다 가능 할때 각각 더하고, 뺴는 것을 놓았습니다.

그래서 j를 N만큼 순회할 때마다 재귀 dp로 해결하려고 했는데요

어떻게 해야 시간초과를 줄일 수 있는지 궁금합니다..

dp[i][j] = -1인 것들은 순회를 안하고 그냥 넘어가게 했는데 어떤 점에서 시간을 더 줄일 수 있을까요?

------------------------------------------------------- 수정 ---------------------------------------------

i는 0, 1 의 값을 갖도록 바꾸었습니다.

어떤 부분에서 반복적인 예시가 생기는지 잘 모르겠습니다..

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include<iomanip>

using namespace std;

/*
- endl 대신 '\n' 사용하기
- cin.tie(0) 사용
- 테스트 케이스 있는 문제일 시 전역변수 초기화 신경쓰기
- (A + B + C) % D = ((A + B) % D + C) % D
- 문자열 출력 문제는 정답 문자열 복사해서 코드에 넣기
- 괄호 사용 유의하기
- 문자열은 함수로 넘길 때 const & 잘 사용하기

- 최악의 경우 int 값 초과하는지, 배열 인덱스 초과하는지 확인
- n 범위 확인 (0인 경우), 양수음수 정수소수 확인, 불가케이스 -1 출력 등 확인
- 큰 배열 선언 시 전역선언, 테케 많을 시 초기화, 배열 용량 max N + 5
*/

#define MOD 1000000007
#define INT_MAX 987654321
#define MAX 100005

typedef long long int ll;
typedef pair<int, int> pii;

int N, S, M;
vector<int> V;
int dp[2][101];
int max_val = -1;
// 테스트 케이스 초기화 시
void init()
{
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 101; j++) {
			dp[i][j] = -1;
		}
	}
}
void find_Max(int now_idx, int before_val) {
	if (before_val == -1) {
		return;
	}
	if (now_idx == N) {
		int temp_max_val = -1;
		for (int i = 0; i < 2; i++) {
			if (dp[i][now_idx - 1] != -1) {
				if (temp_max_val < dp[i][now_idx - 1]) {
					temp_max_val = dp[i][now_idx - 1];
				}
			}
		}
		if (max_val < temp_max_val) {
			max_val = temp_max_val;
		}
		return;
	}
	int volume_dif = V[now_idx];
	if (before_val - volume_dif >= 0) {
		dp[0][now_idx] = before_val - volume_dif;
	}
	if (before_val + volume_dif <= M ) {
		dp[1][now_idx] = before_val + volume_dif;
	}
	now_idx++;

	for (int j = 0; j < 2; j++) {
		if (dp[j][now_idx - 1] != -1) {
			find_Max(now_idx, dp[j][now_idx - 1]);
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	init();
	cin >> N >> S >> M; // 곡의 개수, 시작 볼륨, M보다 큰 값
	int input;
	for (int i = 0; i < N; i++) {
		cin >> input;
		V.push_back(input);
	}
	if (S - V[0] >= 0) {
		dp[0][0] = S - V[0];
	}
	if (S + V[0] <= M) {
		dp[1][0] = S + V[0];
	}
	
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 2; j++) {
			if (dp[j][i - 1] != -1) {
				find_Max(i, dp[j][i - 1]);
			}
		}
	}
	cout << max_val << '\n';
	return 0;
}

dksdmssh1212 3년 전 0

제가 시간초과가 나는 이유를 알았습니다.

첫 번째 단계에서

S + V[0], S- V[0]

그 다음단계에서는

S+V[0] +- V[1], S - V[0] +- V[1]

그럼 만약 100까지의 곡에서는

2의 100-1 승개의 케이스를 전부 다 고려해 줘야 하는 것 같습니다.

그래서 차라리 dp[i][j]에서

j를 음량으로 설정해 주고,

이전 단계에서 사용한 음량 dp[i-1]에 저장해서 해결했습니다.

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

문제

문제

출처

ICPC

시간초과 질문드립니다.

dksdmssh1212 3년 전 0

dksdmssh1212 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말