글 읽기 - [질문] 1426번 C++ 시관초과에 대해서 질문있습니다.

jongyeon95 4년 전 0

1426번에 대하여 질문있습니다.

일단 1426번은 재귀를 통하여 해결하고자 접근 하였고 임의로 넣어본 20개의 예시가 모두 잘 나오는 것을 확인하였습니다.

시간 초과가 계속 뜨는데 재귀로 접근을 한 것 자체가 잘못된것인지 제가 예외 사항을 고려하지 못하여 시간초과가 생기는 건지 궁금합니다!

어디 부분이 시간 초과를 일으키는지 혹은 어떠 어떠한 방법으로 문제를 해결하면 좋다는 조언을 해주시면 감사하겠습니다.!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int bucket[1000];
char result[1000];
//bool resultCheck=true;
bool resultCheck2=true;
vector<pair<pair<int,char>,bool>> v;

bool compare(pair<pair<int,char>,bool> p1, pair<pair<int,char>,bool> p2){

   if(p1.first.second==p2.first.second)
      return p1.first.first < p2.first.first;
   return p1.first.second < p2.first.second;

}

void InitResult(int n){
	for (int i = 0; i < n; i++)
   {
      result[i]='!';
   }
}


void InitCard(int n){
	for (int i = 0; i < n; i++)
   {
      int tempInt;
      char tempChar;
      cin >> tempInt >> tempChar;
      v.push_back(pair<pair<int,char>,bool>(make_pair(tempInt,tempChar),true));
   }
}

void InitBucket(int n){
	for(int i=0; i<n; i++){
		cin >>bucket[i];
	}
}


void solve(int start){
	if(resultCheck2){
		bool temp=true;
		if(start==n){
			for (int i = 0; i < n; ++i){
				if(result[i]=='!'){temp=false;}}
			if(temp){
				resultCheck2=false;
				return;
			}		
		}
		else{
		for(int i=0;i<n;i++){
			if(resultCheck2){
				if(v[i].second){
					if(v[i].second&&bucket[start]<=v[i].first.first){
						result[start]=v[i].first.second;
						v[i].second=false;
						solve(start+1);
						v[i].second=true;
						}
					}
				}
			}
		}
		if(result[start]=='!'){return;}
	}
}


int main(){
   
   cin >> n;
   InitCard(n);
   InitBucket(n);
   InitResult(n);
   sort(v.begin(),v.end(),compare);
   
   solve(0);

if(!resultCheck2){
	for (int i = 0; i < n; i++){
      cout <<result[i];
   }
}
   else
   	cout << -1;

}

sait2000 4년 전 1

방법이 틀렸습니다. 완전탐색을 할 필요가 없고, 탐욕법을 이용해서 시간을 O(n^2)까지 줄여야 합니다.

jongyeon95 4년 전 0

그렇군요 감사합니다 !! 다시 한번 탐욕법을 사용해보고 후기 작성하겠습니다!!

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

문제

문제

출처

ICPC

[질문] 1426번 C++ 시관초과에 대해서 질문있습니다.

jongyeon95 4년 전 0

sait2000 4년 전 1

jongyeon95 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말