[BAEKJOON] 1253, 2529

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[gold4, 1253 좋다] - 두 포인터

최대한 이분탐색의 핵심 값인 mid를 활용하여 수행시간을 줄여보려 했으나,
mid를 활용하는 경우, 값을 건너뛰는 과정에서
기준 값과 두 수의 합이 일치하는 경우를 전부 확인할 수 없기 때문에, 예외 케이스가 존재합니다.

따라서, 가장 합리적인 방법이 두 포인터를 활용하는 것이며
자기 자신을 제외한 값을 활용해야 한다는 점에 주의하고
algorithm 헤더에 포함된 upper와 lower를 활용하여 동일한 케이스를 합산하는 방법을 활용하세요.

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;

int N, answer;
int ary[2001];

int main() {
	scanf("%d", &N);
	for (int n = 0; n < N; n++)
		scanf("%d", &ary[n]);

	sort(ary, ary + N);
	
	for (int n = 0; n < N; n++) {
		int pivot = ary[n];
		int left = 0;
		int right = N - 1;
		while (left < right) {
			int res = ary[left] + ary[right];
			if (left == n || pivot > res) {
				left++;
				continue;
			}
			if (right == n || pivot < res) {
				right--;
				continue;
			}
			if (pivot == res) {
				int upper = upper_bound(ary, ary + N, ary[n]) - ary;
				int lower = lower_bound(ary, ary + N, ary[n]) - ary;
				answer += upper - lower;
				n = upper - 1;
				break;
			}
		}
	}
	printf("%d", answer);
}

 

[sliver1, 2529 부등호] - 브루트포스

문제에서 나올 수 있는 최대 값은 9876543210, 최소는 00000000000이다.

숫자로 치환하면 int는 가뿐히 넘기 때문에, string을 활용하여 값을 비교할 땐 stoll을 사용해 주어야 하는 것에 유의하자.

 

결국 문제는, 중복이 존재하지 않는 모든 조합을 찾아내는 것인데

현재 추가되는 값의 위치가 cnt라면,

숫자배열의 cnt-1위치와 cnt 위치의 값을

등호배열의 cnt 위치의 등호를 사용하여 비교하고,

참이라면 다음 조합을 찾아가는 방법을 사용하자.

#include <iostream>
#include <string>
#pragma warning(disable:4996)

using namespace std;

int K;
string max_answer = "0000000000", min_answer = "9876543210";
char sign[10];
int answer[10];
bool visit[10];

void selectNumber(int value, int cnt, string result);
bool compareValue(int a, int b, char symbol);

int main() {
	scanf("%d", &K);
	for (int k = 0; k < K; k++) {
		scanf(" %c", &sign[k]);
	}

	for (int i = 0; i <= 9; i++) {
		visit[i] = true;
		selectNumber(i, 1, to_string(i));
		visit[i] = false;
	}

	cout << max_answer << '\n' << min_answer;
}

void selectNumber(int value, int cnt, string result) {
	answer[cnt - 1] = value;

	if (cnt == K + 1) {
		if (stoll(max_answer) < stoll(result)) {
			max_answer = result;
		}
		if (stoll(min_answer) > stoll(result)) {
			min_answer = result;
		}
		return;
	}

	for (int i = 0; i <= 9; i++) {
		if (!visit[i]) {
			if (compareValue(value, i, sign[cnt - 1])) {
				visit[i] = true;
				selectNumber(i, cnt + 1, result + to_string(i));
				visit[i] = false;
			}
		}
	}
}

bool compareValue(int a, int b, char symbol) {
	switch (symbol) {
	case '<':
		return a < b;
	case '>':
		return a > b;
	default:
		return false;
	}
}