BOJ 1332) c++ 풀자

시간 제한 - 2s

메모리 제한 - 128MB

 

 

---

풀이

1. 처음에는 무조건 1번을 풀어야 함

2. 최소, 최대 값의 차이가 각 단계의 해가 되기 때문에 Memorization을 사용이 어려움

    ex) 10 5 15 0 20 ...의 경우, 10 다음에 5/ 15 어떤 문제를 푸는 것이 최적인지 알기 어렵다.

    각 단계까지의 depth, 최대 값, 최소 값을 기준으로 기록하면 최대 1000 * 1000 * 50의 3차원 벡터가 생겨 128MB 메모리를 초과함

3. 따라서 brute force로 진행하되 백트래킹 최적화로 덜 계산하는 편이 좋겠다고 생각함

입력

총 문제의 갯수(N)와 최대-최소 간 기준 값(V)

흥미도 X0 X1 X2 .. Xn

자료구조

각 문제의 흥미도를 담기 위한 int형 배열

 

로직

1. 맨 처음은 무조건 1번을 풀어야함(bottom -> top 순서로 진행)

2. 현재까지 풀었던 문제 중 최소 값과 최대 값의 차이가 V 이상일 때까지 문제를 풀며, 값의 차이가 V보다 크지 않다면 결국 모든 문제를 풀게 됨

3. N이 최대 50이기 때문에 완전 탐색을 수행해 모든 해를 탐색할 시 O(N^50)이므로 prune을 통해 계산 횟수 줄임

  3.1) 전체 문제의 최소 값과 최대 값의 차이가 V보다 작다면 그냥 N 출력하고 종료

  3.2) 현재 문제를 푼 수가 현재까지의 해보다 커질 경우, 최적해일 수 없으므로 그대로 종료

  3.3) 현재 최소 값과 최대 값이 V 이상일 경우, 문제를 더 푸는 것이 최적해일 수 없으므로 그대로 종료

---

 

코드

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int N, V;
int optimal;
vector<int> questions;

void DFS(int minV, int maxV, int qNum, int depth) {
	if (qNum >= N) return ;	//	Index Exception
	if (depth >= optimal) return ;	//	로직 3.2) 최적해보다 문제를 많이 풀고 있다면 이미 최적해가 아님

	minV = min(minV, questions[qNum]);
	maxV = max(maxV, questions[qNum]);	
	if (maxV - minV >= V) {	//	로직 3.3) 이미 V 이상이라면 문제를 더 풀 필요 X
		optimal = depth;
		return ;
	}
	DFS(minV, maxV, qNum + 2, depth + 1);	//	+2부터 수행해서 연산 조금이라도 줄임
	DFS(minV, maxV, qNum + 1, depth + 1);
}

int main() {
	cin >> N >> V;
	optimal = N;	//	최악의 경우 N문제를 전부 풀기 때문에 N으로 초기화
	questions.resize(N);
	for (auto& it : questions) cin >> it;
	if (!(*max_element(questions.begin(), questions.end()) - *min_element(questions.begin(), questions.end()) < V))
		DFS(questions[0], questions[0], 0, 1);	//	로직 3.1) 최대, 최소 값이 V보다 작다면 어차피 N문제 다 풂
	cout << optimal << '\n';
	return 0;
}

 

시간 복잡도

prune이 이루어지는 조건이 있기에 계산이 어렵지만, 완전 탐색을 상정하면 O(2^N)

 

---

문제 푼 사람이 얼마 없어서 혹시? 했는데 인터넷에 풀이 아무것도 없길래 조회수 꿀빨아서 구글애드 통과댔으면 좋겠다