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

 

10816번: 숫자 카드 2

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,

www.acmicpc.net

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	unordered_map<int, int> list;
	int N, M;
	int search;

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int num;
		cin >> num;
		if (list[num] > 0) list[num]++;
		else list[num] = 1;
	}

	cin >> M;
	for (int i = 1; i <= M; i++) {
		cin >> search;
		if (list[search] > 0) cout << list[search] << " ";
		else cout << "0 ";
	}

	return 0;
}

'APS > 백준' 카테고리의 다른 글

[21924] 도시 건설 C++  (0) 2022.03.05
[14716] 현수막 C++  (0) 2022.03.05
[3745] 오름세 C++  (0) 2022.03.02
[17245] 서버실 C++  (0) 2022.02.21
[2110] 공유기 설치 C++  (0) 2022.02.13

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

 

3745번: 오름세

입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다.

www.acmicpc.net

- lower_bound 사용하기

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

int main() {

	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

	int n;

	while (cin >> n) {
		vector<int> vec;

		for (int i = 0; i < n; i++) {
			int num;
			cin >> num;
			if (vec.empty() || vec.back() < num)
				vec.push_back(num);
			else {
				// vector에서 입력받은 값과 같거나 큰 수 중 가장 작은 수의 위치
				int tmp = lower_bound(vec.begin(), vec.end(), num) - vec.begin();
				vec[tmp] = num;
			}
		}

		cout << vec.size() << endl;
	}

	return 0;
}

 

- 시간초과

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

int main() {

	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

	int n;

	while (cin >> n) {
		int arr[100001];
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}

		int MAX = 1;
		int len[100001] = { 0 };
		for (int i = 1; i < n; i++) {
			len[i] = 1;
			for (int j = i - 1; j >= 0; j--) {
				if (arr[i] > arr[j])
					len[i] = max(len[i], len[j] + 1);

				if (len[i] > MAX)
					MAX = len[i];
			}
		}

		cout << MAX << "\n";
	}

	return 0;
}

'APS > 백준' 카테고리의 다른 글

[14716] 현수막 C++  (0) 2022.03.05
[10816] 숫자 카드2 C++  (0) 2022.03.03
[17245] 서버실 C++  (0) 2022.02.21
[2110] 공유기 설치 C++  (0) 2022.02.13
[2805] 나무 자르기 C++  (0) 2022.02.13

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

 

17245번: 서버실

서버실에는 모두 85대의 컴퓨터가 있고, 3분이 지나면 전체의 58%인 50대의 컴퓨터가 정상 작동된다.

www.acmicpc.net

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

using namespace std;

int main() {
	int N;
	int arr[1000][1000];

	cin >> N;

	int MAX = -1;
	
	// long long은 실패
	double sum = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
			MAX = max(MAX, arr[i][j]);
			sum += arr[i][j];
		}
	}

	int left = 0;
	int right = MAX;

	int answer = 21e8;

	while (left <= right) {
		long long cnt = 0;

		int middle = (left + right) / 2;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cnt += min(middle, arr[i][j]);
			}
		}

		if (cnt >= round(sum / 2)) {
			answer = min(middle, answer);

			right = middle - 1;
		}

		else {
			left = middle + 1;
		}

	}

	cout << answer;

	return 0;
}

'APS > 백준' 카테고리의 다른 글

[10816] 숫자 카드2 C++  (0) 2022.03.03
[3745] 오름세 C++  (0) 2022.03.02
[2110] 공유기 설치 C++  (0) 2022.02.13
[2805] 나무 자르기 C++  (0) 2022.02.13
[2512] 예산 C++  (0) 2022.02.09

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

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가

www.acmicpc.net

- 이분탐색 (cnt >= C)

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

using namespace std;

int main() {
	int N, C;
	int arr[200001];

	cin >> N >> C;
	
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr, arr + N);

	int left = 0;
	int right = arr[N - 1];

	int answer = -21e8;

	// 첫집은 무조건 설치해야 최대거리 구할수 있음
	while (left <= right) {
		int before = 0;
		int cnt = 1;

		int middle = (left + right) / 2;

		for (int i = 1; i < N; i++) {
			if (arr[i] - arr[before] >= middle) {
				before = i;
				cnt++;
			}
		}


		// cnt == C가 아니라 cnt >= C가 맞음 (최소길이만 비교하면 되기 때문)
		if (cnt >= C) {
			if (middle > answer)
				answer = middle;

			left = middle + 1;
		}

		else {
			right = middle - 1;
		}

	}

	cout << answer;

	return 0;
}

 

- dfs (시간초과)

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

using namespace std;

int N, C;
int arr[200001];
int path[200001];
int MAX = -21e8;

void dfs(int le, int st) {
	if (le == C) {
		int MIN = 21e8;

		for (int a = 1; a < C; a++) {
			MIN = min(MIN, (path[a] - path[a - 1]));
		}

		if (MIN > MAX)
			MAX = MIN;

		return;
	}

	for (int i = st; i < N; i++) {
		path[le] = arr[i];
		dfs(le + 1, i + 1);
	}
}

int main() {

	cin >> N >> C;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr, arr + N);

	path[0] = arr[0];
	dfs(1,1);
	
	cout << MAX;


	return 0;
}

'APS > 백준' 카테고리의 다른 글

[3745] 오름세 C++  (0) 2022.03.02
[17245] 서버실 C++  (0) 2022.02.21
[2805] 나무 자르기 C++  (0) 2022.02.13
[2512] 예산 C++  (0) 2022.02.09
[1920] 수 찾기 C++  (0) 2022.02.08

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

 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

 

-> sum이나 tmp는 int범위를 초과할 수 있어 long long으로 변환 후 통과

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

using namespace std;

int main() {
	int N, M;
	int arr[1000001];
	cin >> N >> M;

	long long sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		sum += arr[i];
	}

	sort(arr, arr + N);

	if (sum == M) {
		cout << "0";
		return 0;
	}

		int left = 0;
		int right = arr[N - 1];

		int answer;
		while (left <= right) {
			long long tmp = 0;
			int middle = (left + right) / 2;

			for (int i = 0; i < N; i++) {
				tmp += min(arr[i], middle);
			}

			if (sum - tmp >= M) {
				answer = middle;
				left = middle + 1;
			}

			else {
				right = middle - 1;
			}

	}

		cout << answer;
	
	return 0;
}

'APS > 백준' 카테고리의 다른 글

[17245] 서버실 C++  (0) 2022.02.21
[2110] 공유기 설치 C++  (0) 2022.02.13
[2512] 예산 C++  (0) 2022.02.09
[1920] 수 찾기 C++  (0) 2022.02.08
[3273] 두 수의 합  (0) 2021.08.25

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

 

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

using namespace std;

int main() {
	int N, M;
	int arr[10001];
	cin >> N;

	int sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		sum += arr[i];
	}

	cin >> M;
	sort(arr, arr + N);

	if (sum <= M) {
		cout << arr[N - 1];
		return 0;
	}

	else {
		int left = 0;
		int right = arr[N - 1];

		int answer;
		while (left <= right) {
			sum = 0;
			int middle = (left + right) / 2;

			for (int i = 0; i < N; i++) 
				sum += min(arr[i], middle);

			if (sum == M) {
				cout << min(arr[N - 1], middle);
				return 0;
			}

			else if (sum > M)
				right = middle - 1;

			else {
				left = middle + 1;
				answer = min(arr[N - 1], middle);
			}
		}

		cout << answer;
	}
	
	return 0;
}

'APS > 백준' 카테고리의 다른 글

[2110] 공유기 설치 C++  (0) 2022.02.13
[2805] 나무 자르기 C++  (0) 2022.02.13
[1920] 수 찾기 C++  (0) 2022.02.08
[3273] 두 수의 합  (0) 2021.08.25
[단계별로 풀어보기] 백트래킹  (0) 2021.08.20

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

 

1920번: 수 찾기

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들

www.acmicpc.net

- vector사용시 기본배열보다 시간이 더 오래걸리는 이유

 -> vector는 동적 배열로 공간이 부족할때마다 2배로 확장을 함

- cin/ cout이 printf보다 오래걸리는 이유

 -> scanf(0.798s)/ cin(2.051s)

 -> ios_base::sync_with_stdio(false); cin.tie(null); 추가시 속도향상(0.796s)

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

using namespace std;

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

	int N, M;
	// vector<int> arr;
	int arr[100001];

	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr[i] = num;
	}

	sort(arr, arr + N);

	cin >> M;

	for (int i = 0; i < M; i++) {
		int flag = 0;
		int searchNum;
		cin >> searchNum;
		int left = 0, right = N - 1;
		while (left<=right) {
			int middle = (left + right) / 2;
			if (searchNum == arr[middle]) {
				cout << "1" << "\n";
				flag = 1;
				break;
			}
			else if (searchNum < arr[middle])
				right = middle - 1;
			else
				left = middle + 1;
		}
		if(flag==0)
			cout << "0" << "\n";
	}

	return 0;
}

'APS > 백준' 카테고리의 다른 글

[2805] 나무 자르기 C++  (0) 2022.02.13
[2512] 예산 C++  (0) 2022.02.09
[3273] 두 수의 합  (0) 2021.08.25
[단계별로 풀어보기] 백트래킹  (0) 2021.08.20
[단계별로 풀어보기] 브루트 포스  (0) 2021.08.16

- PASS

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int cnt;
int T;
int S;

void dfs(int le, vector<int> numbers, int sum) {
    if (le == S) {
        if (sum == T)
            cnt++;
        return;
    }
    
    dfs(le + 1, numbers, sum + numbers[le] );
    dfs(le + 1, numbers, sum - numbers[le] );
        
}


int solution(vector<int> numbers, int target) {
    int answer = 0;

    cnt = 0;
    T = target;
    S = numbers.size();
    dfs(0, numbers, 0);

    answer = cnt;
    return answer;
}

 

- TC1,2 시간초과 75.0/100

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int cnt;
int T;
int S;

void dfs(int le, int st, vector<int> numbers, int sum) {
    if (le == S) {
        if (sum == T)
            cnt++;
        return;
    }

    for (int i = st; i < S; i++) {
        for (int j = 0; j < 2; j++){
            if(j==0)
                dfs(le + 1, i + 1, numbers, sum + numbers[i] );
            else
                dfs(le + 1, i + 1, numbers, sum - numbers[i] );
        }
    }
}

int solution(vector<int> numbers, int target) {
    int answer = 0;

    cnt = 0;
    T = target;
    S = numbers.size();
    dfs(0, 0, numbers, 0);

    answer = cnt;
    return answer;
}

+ Recent posts

티스토리툴바