작은시작

문제

https://www.acmicpc.net/problem/4949

풀이

초반부터 설계를 제대로 하고 풀지 않아서 오래 걸렸다. 

쉽게 금방 풀릴줄알아서 바로 코드에 들어간 게 문제였다. 

신경 써야 할 점은

1. 공백 또한 입력받아야 한다. (string 헤더의 getline() 사용 필요 )

2. 스택의 경우의 수를 모두 생각 ->  ')' or ']'가 등장하였을 때 스택에 문자가 있긴 한지, 있다면 그사이 문자열 또한 균형이 잡혀있는지 판단하여야 한다.

코드

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<stack>
using namespace std;
string arr;
stack<char> st;
vector<bool> result;
int main() {


	while (1) {
		bool flag = false;
		
			//<srting> 헤더의 getline()을 활용한 공백문자 입력 포함 , 개행(enter)까지 문자를 받음 
			
			getline(cin, arr);
			
			
		if (arr.size() == 1 && arr[0]=='.') break; //종료조건

		for (int i = 0; i < arr.size(); i++) {

			if (arr[i] == '(' || arr[i] == '[') st.push(arr[i]);
			
			if (!st.empty()) { 
				if (arr[i] == ')' && st.top() == '(') {
					st.pop();
				}
				else if (arr[i] == ']' && st.top() == '[') {
					st.pop();
				}
				else if (arr[i] == ')' && st.top() != '(') {
					flag = true;
					break;
				}
				else if (arr[i] == ']' && st.top() != '[') {
					flag = true;
					break;
				}
			}
			else { //비었을때
				if (arr[i] == ')' || arr[i] == ']') {
					flag = true;
					break;
				}
			}

		
			

		}

		if (st.size() == 0 && flag == false) result.push_back(true);
		else result.push_back(false);

		//다음을 위해 스택,문자열비우기 

		while (!st.empty()) {
			st.pop();
		}
		arr.clear();

	}

	for (int j = 0; j < result.size(); j++) {
		if (result[j] == true) cout << "yes" << endl;
		else cout << "no" << endl;
	}

	return 0;
}

문제

https://www.acmicpc.net/problem/2839

풀이

그리디로 풀었다. 5kg으로 먼저 나누어 준후, 3kg으로 나누어지는지 판단하다.

나머지가 남는다면 5kg 봉지를 하나씩 빼가면서 다시 탐색한다.

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N;
int main() {
	cin >> N;
	int a = N / 5;
	int b = 0;
	int cnt = 0;
	while (1) {
		

		if (a < 0) {
			cnt = -1;
			break;
		}
		else {
			if ((N - (5 * a)) % 3 == 0) {
				b = (N - (5 * a)) / 3;
				break;
			}
			a--;
		}
	}
	cout << a + b;


	



	return 0;
}

문제

https://www.acmicpc.net/problem/2805

풀이

문제를 보면 나무의 높이, 절단기 높이 등 int의 숫자 범위를 넘는다.  또한 적어도+최댓값 등을 찾을 때는 이분 탐색을 의심해보자

두 가지 실수하지 않도록 조심하자

1. long long 변수형이 어디 어디에 필요한지

2. 나무절단시 if문을 통해 음수 걸러주기 

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int H;
int N;
long long M; //숫자가 너무 큰 탐색 -> 이분탐색 의심
vector<long long> arr;
long long answer;
int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		long long abc;
		cin >> abc;
		arr.push_back(abc);
	}

	sort(arr.begin(), arr.end(),greater<>());

	//이분탐색
	long long low = 0;
	long long high = arr[0];
	while (low <= high) {
		long long middle = (low + high) / 2;
		
		long long sum = 0;
		for (int i = 0; i < N; i++) {
			if(arr[i]-middle>0) sum += arr[i] - middle;

		}
		if (sum >=M) {
			low = middle + 1;
			answer = middle;
		}
		else { // 나무 부족, 절단기 높이 줄임
			high = middle - 1;

		}



	}
	cout << answer;





	return 0;
}

문제

https://www.acmicpc.net/problem/2798

풀이

기본적인 Bruth-force 문제였다. 전부 탐색해보면서 대신 모두 같은 카드를 고르는 case는 빼고 탐색하자. 

또한 Sort 를 사용하여 빠르게 최대 값을 찾을 수 있다.

코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int N, M;
vector<int> arr;
vector<int> result;
int main() {
	cin >> N >> M;


	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		arr.push_back(a);

	}

	//완전탐색
	int sum = 0;
	for (int y = 0; y < N - 2; y++) {
		for (int x = 1; x < N - 1; x++) {
			for (int z = 2; z < N; z++) {
				if (y == x || y == z || x == z) continue;
				sum = arr[y] + arr[x] + arr[z];
				if(sum<=M) result.push_back(sum);
			}
		}
	}



	sort(result.begin(), result.end());
	cout << result[result.size() - 1];


	return 0;
}