언제나 처음처럼

[문제 링크]

https://onlytrying.tistory.com/55

1654번: 랜선 자르기, 2805번: 나무 자르기 유형의 문제와 같은 알고리즘을 사용한다.

분배하는 예산이 커질 수록 총 필요한 예산도 커진다. 즉, 분배하는 예산과 총 필요한 예산은 서로 비례한다.

금액 N으로 예산을 분배했을 때 만약 총 필요한 예산이 입력받은 국가 예산보다 크다면 N 이상의 금액을 고려하지 않아도 되기 때문에 이분 탐색을 진행할 수 있다.

먼저, 지방 예산을 vector 배열에 저장하면서, 변수 sum에 누적한다.

만약 입력받은 국가 예산이 sum보다 크다면 정답은 가장 큰 지방 예산이 되기 때문에 탐색을 하지 않아도 된다.

이 경우가 아니라면 start를 1, end를 가장 큰 지방 예산으로 이분 탐색을 진행하여 가능한 최대 예산을 구해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
	int N;
	cin >> N;
	
	vector<int> money(N);
	int total = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> money[i];
		total += money[i];
	}

	sort(money.begin(), money.end());

	int maxMoney;
	cin >> maxMoney;

	if (total <= maxMoney)
		cout << money[N - 1];
	else
	{
		int start = 1, end = money[N - 1], result;
		
		while (start <= end)
		{
			int mid = (start + end) / 2, sum = 0;
			for (int i = 0; i < N; i++)
			{
				if (money[i] <= mid)
					sum += money[i];
				else
					sum += mid;
			}
			
			if (sum <= maxMoney)
			{
				result = mid;
				start = mid + 1;
			}
			else
				end = mid - 1;
		}

		cout << result << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 46 day

[문제 링크]

https://onlytrying.tistory.com/54

나무 자르기 문제와 비슷한 유형의 문제였다.

랜선을 자르는 길이가 길어질수록 만들어지는 랜선의 갯수는 무조건 작아지기 때문에 자르는 길이와 만들어지는 랜선의 갯수는 서로 반비례한다는 것을 알 수 있다.

알고리즘은 나무 자르기 문제와 동일하다.

차이점으로는 0cm 길이의 랜선을 가져갈 수는 없기 때문에 start의 초기값을 0이 아닌 1로 해야 하고, 입력되는 정수의 최댓값이 크므로 unsigned int나 long long 자료형을 사용해야 한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
	int K, N;
	cin >> K >> N;
	
	vector<int> utp(K);
	for (int i = 0; i < K; i++)
		cin >> utp[i];
	
	sort(utp.begin(), utp.end());
	
	long long start = 1, end = utp[K - 1];
	int result;

	while (start <= end)
	{
		long long mid = (start + end) / 2;
		int sum = 0;

		for (int i = 0; i < K; i++)
			sum += utp[i] / mid;

		if (sum >= N)
		{
			result = mid;
			start = mid + 1;
		}
		else
			end = mid - 1;
	}
	cout << result << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 46 day

[문제 링크]

함정이 있는 이분 탐색 문제였다.

나무를 자르는 높이가 낮을수록 얻어가는 나무는 증가한다. 즉 나무를 자르는 높이(N)과 얻어가는 나무의 양은 반비례한다.

따라서, 어떤 높이(mid)를 기준으로 나무를 잘랐을 때 얻어가는 나무의 양이 필요한 양(M)보다 작다면 mid보다 높이 자르는 경우는 고려하지 않아도 되며, 이 사실을 바탕으로 이분 탐색을 사용하는 조건을 만족하게 된다.

알고리즘은 다음과 같다.

먼저 나무들의 높이를 vector에 입력받은 다음 오름차순으로 정렬하자.

그 다음 가장 낮은 높이(lower)를 0으로 하고, 가장 높은 높이(upper)를 벡터의 마지막 원소로 하여

(lower + upper) / 2 를 mid 로 이분 탐색을 시작한다.

vector의 모든 원소에 대하여 v[i] - mid가 0보다 클 경우 sum 변수에 값을 누적 시킨다.

만약 sum이  M보다 작을 경우 mid 높이보다 같거나 높은 경우는 버려도 무방하므로 upper 값을 mid - 1로 바꿔준다.

sum이 M보다 같거나 클 경우 조건을 만족하므로 result 변수에 mid를 저장하고, 최대 높이를 찾기 위해 lower 값을 mid + 1로 바꿔준다.

(ps. 여기서 함정이 있는데 적어도 M개를 가져가야 하므로, sum이 M보다 크거나 같은 경우에 result 변수를 갱신해야한다. 작거나 같은 경우에 result 변수를 갱신하게 되면 오답이 출력된다.)

끝으로, lower이 upper보다 커질 때가지 위 작업을 반복하게 되면 result 변수에는 적어도 M미터의 나무를 얻기 위한 최대의 높이가 저장된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;
	vector<int> tree(N);

	for (int i = 0; i < N; i++)
		cin >> tree[i];

	sort(tree.begin(), tree.end());
	
	int lower = 0, upper = tree[N-1], result;
	while (lower <= upper)
	{
		int mid = (lower + upper) / 2;
		long long sum = 0;
		for (int i = 0; i < N; i++)
		{
			if (tree[i] < mid) continue;
			sum += tree[i] - mid;
		}
		if (sum >= M)
		{
			result = mid;
			lower = mid + 1;
		}
		else
		{
			upper = mid - 1;
		}
	}
	cout << result << endl;
	return 0;
}

알고리즘 200일 프로젝트 - 45 day

[문제 링크]

간단한 이분탐색 문제였다.

입력받은 숫자들을 vector에 저장하고, 정렬한 다음 binary_search() 함수를 통해 찾고자 하는 숫자의 존재 여부를 파악하고 반환되는 bool 값을 출력해주면 원하는 결과를 얻을 수 있다.

이 문제처럼 입출력이 많이 발생하는 문제를 풀 때는 ios_base::sync_with_stdio(0); 과 cin.tie(NULL); 을 꼭 추가해주는 것이 좋다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	vector<long long> arr;
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		arr.push_back(num);
	}
	sort(arr.begin(), arr.end());
	
	int M;
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int num;
		cin >> num;
		cout << binary_search(arr.begin(), arr.end(), num) << '\n';
	}

	return 0;
}

알고리즘 200일 프로젝트 - 45 day

[문제 링크]

맞추고도 머리가 띵했던 문제였다. 왜냐하면 설마 이게 맞겠어? 하고 제출한 코드가 정답 처리를 받았기 때문이다.

알고리즘(?)은 다음과 같다

낮에 올라가는 높이 = A, 밤에 떨어지는 높이 = B, 총 올라가야 하는 높이 = V 라고 할 때,

정상에만 올라가면 떨어질 일이 없기 때문에 (V-A) 높이 이상으로만 올라간다면 올라가는데 걸린 DAY에 추가로 하루가 더 걸리게 된다.

따라서 최소로 올라가야할 높이 (V-A)를 먼저 구해주고, 구한 높이를 (A-B)로 나눈 몫과 나머지를 구한다.

이 때 구한 몫이 DAY가 되고, 나머지가 0이라면 최소 높이에 도달했으므로 DAY+1을 출력, 나머지가 0이 아니라면 최소 높이에 도달하지 못한 것이므로 하루가 더 걸리게 되어 DAY+2를 출력해주면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

int main(void)
{
	int A, B, V;
	cin >> A >> B >> V;

	int end = V - A, up = A - B;
	int day = end / up, check = end % up;
	if (check == 0) 
		cout << ++day << endl;
	else
	{
		day += 2;
		cout << day << endl;
	}
	return 0;
}

알고리즘 200일 프로젝트 - 45 day

[문제 링크]

https://onlytrying.tistory.com/50

10815번: 숫자 카드 문제의 업그레이드 버전 문제이다.

이 문제는 존재 유무뿐만이 아니라 존재하는 갯수까지 세야한다.

필자는 간단히 multiset으로 원소의 중복을 허용하고 count() 멤버함수를 사용하여 구현하려했으나 시간초과가 발생하였다.

연관 컨테이너(map,set 등)는 삽입, 삭제 연산 시 상당히 많은 작업이 필요할 수 있기 때문에 전부 다 입력받고 정렬하는 편이 훨씬 더 빠르다는 것을 간과하고 있었다.

따라서 vector에 정수를 저장한 다음 정렬한 후, 정렬된 범위에서 동작하는 알고리즘인 equal_range() 를 사용하여 upper_bound 반복자와 lower_bound 반복자의 차이가 원소의 갯수인 것을 이용해 문제를 해결하였다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	vector<int> card;
	int N; 
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		card.push_back(num);
	}
	sort(card.begin(), card.end());
	int M; 
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int num;
		cin >> num;
		pair<vector<int>::iterator, vector<int>::iterator> range = equal_range(card.begin(), card.end(), num);
		if (range.first != range.second) cout << range.second - range.first << ' ';
		else cout << "0 ";
	}
	return 0;
}

알고리즘 200일 프로젝트 - 44day

[문제 링크]

간단한 이분탐색 문제였다. 입력받은 숫자들을 오름차순으로 정렬하고, 그 다음으로 입력받는 정수들을 이분 탐색을 통해 검색해 존재할 경우 1, 존재하지 않을 경우 0을 출력해주면 원하는 결과를 얻을 수 있다.

ps. 입력과 출력의 횟수가 크기때문에 ios_base::sync_with_stdio(0); 과 cin.tie(NULL); 을 추가해주는 것이 좋다.

(대부분의 시간초과는 입출력 부분에서 잡아먹는 시간때문에 발생한다.)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	vector<int> card;
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		card.push_back(num);
	}
	sort(card.begin(), card.end());
	int M;
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int num;
		cin >> num;
		bool state = false;
		int start = 0, end = card.size()-1;
		while (start <= end)
		{
			int mid = (start + end) / 2;
			if (num < card[mid])
				end = mid-1;
			else if (num > card[mid])
				start = mid+1;
			else
			{
				cout << "1 ";
				state = true;
				break;
			}
		}
		if (!state) cout << "0 ";
	}

	return 0;
}

또한 c++의 set 컨테이너에 정수를 담고 set의 멤버함수인 find() 를 사용하면 매우 간단하게 구현할 수 있다.

#include <iostream>
#include <set>
using namespace std;
int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	set<int> card;
	int N; 
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		card.insert(num);
	}
	int M; 
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int num;
		cin >> num;
		if (card.find(num) != card.end()) cout << "1 ";
		else cout << "0 ";
	}
	return 0;
}

알고리즘 200일 프로젝트 - 44day

[문제 링크]

c++ stl 컨테이너인 map을 사용하면 쉽게 풀 수 있는 문제라 생각한다.

map 컨테이너는 [ ] 로  key값을 이용해 간단하게 value값을 찾을 수 있으며, O(logN) 시간복잡도를 보장한다.

필자는 key값이 string인 map과 int인 map을 두개 만들어서 입력되는 문제가 string일 경우와 int일 경우 if문을 통해 각각 다른 map컨테이너를 검색하도록 구현하였다.

참고로 시간초과로 고생 하시는 분들께서는 ios_bass::sync_with_stdio(0); cin.tie(NULL); 을 추가하고 cout과 cin을 사용해보는 것을 추천합니다.

#include <iostream>
#include <cstdlib>
#include <map>
#include <string>
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	map<string, int> poketStr;
	map<int, string> poketNum;
	int N, M, num=1;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;
		poketStr.insert(make_pair(str, num));
		poketNum.insert(make_pair(num++, str));
	}

	for (int i = 0; i < M; i++)
	{
		char question[21];
		cin >> question;
		if (question[0] < 'A')
		{
			int qNum = atoi(question);
			cout << poketNum[qNum] << '\n';
		}
		else
		{
			cout << poketStr[question] << '\n';
		}
	}
	return 0;
}

알고리즘 200일 프로젝트 - 43day