5
abcde

4739715

3
zzz

25818

1
i

9

University > 아주대학교 > 2018 Ajou Programming Contest > Division 2 C번

문제의 핵심은 변수 범위를 초과하지 않게 제곱 계산을 하는 것 인듯 하다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int M = 1234567891;
const int R = 31;

long square_mod(int times) {
	long temp = 1;
	for (int i = 0; i < times; i++) { //returns R^times mod (M)
		temp *= R;
		if (temp >= M) {
			temp %= M;
		}
	}
	return temp;
}

int hash(char* target, int size) {
	long temp = 0;
	//수로 바꾸기
	for (int i = 0; i < size; i++) {
		target[i] = (int)target[i] - 96;
	}
	for (int i = 0; i < size; i++) {
		temp += target[i] * square_mod(i);
		if (temp >= M) {
			temp %= M;
		}
	}
	return temp;
}

int main() {
	int size = 0;
	scanf("%d", &size);
	getchar();//개행 문자 제거

	char* target_string = (char*)malloc(sizeof(char) * size+1); 
	if (target_string == NULL)
		return -1;
	
	fgets(target_string, size + 1, stdin);
	target_string[strcspn(target_string, "\n")] = 0;

	printf("%d", hash(target_string, size));

	free(target_string);

	return 0;
}

5
0 4
1 2
1 -1
2 2
3 3

1 -1
1 2
2 2
3 3
0 4

해당 문제는 c의 stdlib헤더의 qsort함수를 사용하면 쉽게 풀 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct Coordinate {
	int x;
	int y;
}MyCoordinate;

int compare(const void* a, const void* b) {
	MyCoordinate* A = (MyCoordinate*)a;
	MyCoordinate* B = (MyCoordinate*)b;
	if (A->y != B->y)
		return A->y - B->y;
	else
		return A->x - B->x;
}

int main() {
	int size;
	scanf("%d", &size);
	MyCoordinate* p = (MyCoordinate*)malloc(sizeof(MyCoordinate) * size);

	for (int i = 0; i < size; i++) {
		scanf("%d %d", &(p[i].x), &(p[i].y));
	}

	qsort(p, size, sizeof(MyCoordinate), compare);

	for (int i = 0; i < size; i++) {
		printf("%d %d\n", p[i].x, p[i].y);
	}


}

5
3 4
1 1
1 -1
2 2
3 3

1 -1
1 1
2 2
3 3
3 4

#include <iostream>
#include <stdlib.h>
#include <algorithm>
using namespace std;

typedef struct Coordinate {
	int x;
	int y;
}UserCoordinate;

bool compare_coordinate(const Coordinate& a, const Coordinate& b) {
	if (a.x != b.x)
		return a.x < b.x;
	return a.y < b.y;
}

int main() {
	int size = 0;
	cin >> size;

	UserCoordinate* p = (UserCoordinate*)malloc(sizeof(UserCoordinate) * size);

	for (int i = 0; i < size; i++) {
		cin >> p[i].x;
		cin >> p[i].y;
	}

	sort(p, p + size, compare_coordinate);

	for (int i = 0; i < size; i++) {
		cout << p[i].x << " ";
		cout << p[i].y << "\n";
	}

	free(p);

	return 0;
}

c언어와 달리 c++의 sort(algorithm 헤더에 정의)함수는 포인터 접근이 아닌 값에 의한 접근을 하므로 

compare함수의 인자는 포인터(*)가 아닌 값(&)으로 정의해야 한다.

부등호의 방향은 오름차순 기준으로 정렬이 필요없는 경우 1을 반환하도록 작성해야 한다.

(c의 qsort의 경우 정렬이 필요없는 경우 음수를 반환하도록)

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

3 0 0 1 2 0 0 2

c++ algorithm 라이브러리에는 binary_search 함수가 존재하지만, 이 함수는 bool타입을 반환하며, 존재 유무만 알려준다.

따라서, upper_bound, lower_bound 함수를 이용하여

찾는 값보다 최초로 큰 값을 가지는 멤버의 포인터(upper_bound) - 최초로 찾는 값을 가지는 멤버의 포인터(lower_bound)를 하면 c++에서 멤버의 크기를 고려해 나눠줘 우리가 찾는 값의 개수를 개산할 수 있다.

물론, 위 로직을 수행하기 위해선 오름차순 혹은 내림차순 정렬이 되어있어야 한다.

#include <iostream>
#include <stdlib.h>
#include <algorithm>
using namespace std;


int main() {
	int size_of_data_table = 0;
	cin >> size_of_data_table;
	int* data_table = (int*)malloc(sizeof(int) * size_of_data_table);
	for (int i = 0; i < size_of_data_table; i++) {
		cin >> data_table[i];
	}
	sort(data_table, data_table + size_of_data_table);

	int size_of_search_table = 0;
	cin >> size_of_search_table;
	int* search_table = (int*)malloc(sizeof(int) * size_of_search_table);
	for (int i = 0; i < size_of_search_table; i++) {
		cin >> search_table[i];
	}
	
	for (int i = 0; i < size_of_search_table; i++) {
		cout << upper_bound(data_table, data_table + size_of_data_table, search_table[i]) - lower_bound(data_table, data_table + size_of_data_table, search_table[i]) << " ";
	}


	free(data_table);
	free(search_table);
	
	return 0;
}

216

198

입력이 1,000,000까지 가능하고, 사용자에게로부터 입력받은 수를 생성하는 수를 구해야 한다.

따라서, 어떤수를 입력에 넣고 그 수의 분해합을 구하는 프로그램을 작성하되, 여섯자리 수까지만 고려하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int calculate_num(int num) {
	int six, five, four, three, two, one;
	six = num / 100000;
	five = num / 10000 - six*10;
	four = num / 1000 - six * 100 - five*10;
	three = num / 100 - six * 1000 - five*100 - four*10;
	two = num / 10 - six*10000 - five*1000 - four*100 - three*10;
	one = num - six*100000 - five*10000 - four*1000 - three*100 - two*10;

	return num + six + five + four + three + two + one;
}

int main() {
	int num;
	scanf("%d", &num);

	for (int i = 1; i <= num; i++) {
		if (calculate_num(i) == num) {
			printf("%d", i);
			return 0;
		}
			
	}
	printf("0");
	return 0;
}

#    define ATOMIC_ADD(type, var, val) ATOMIC_ADD_##type(var, val)

위 전처리문은 메타 프로그래밍 기법으로, 코드를 작성하는 코드이다.

ATOMIC_ADD(int, a, 5);
ATOMIC_ADD(float, b, 4.5);

위와 같이 선언할 시, 

ATOMIC_ADD(type, var, val)은 ATOMIC_ADD_##type(var,val) 로 정의되었으므로

각각

ATOMIC_ADD_int(a,5);

ATOMIC_ADD_float(b,4.5);

와 같이 정의된다.

이와 같은 메타 프로그래밍 기법은 코드의 유연성과 확장성을 높이며, 타입별 연산 함수와 같이 여러 버전이 필요할 경우 관리하기 편하게 만들어준다.

3
40 80 60

75.0

3
10 20 30

66.666667

4
1 100 100 100

75.25

5
1 2 4 8 16

38.75

2
3 10

65.0

4
10 20 0 100

32.5

1
50

100.0

9
10 20 30 40 50 60 70 80 90

55.55555555555556

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main() {
	int num;
	double max, sum, result;
	
	scanf("%d", &num);
	double* val = (double*)malloc(sizeof(double) * num);
	scanf("%lf", &val[0]);
	max = val[0];
	sum = val[0];
	for (int i = 1; i < num; i++) {
		scanf("%lf", &val[i]);
		if (max < val[i])
			max = val[i];
		sum += val[i];
	}
	result = (sum / ((double)num * max)) * 100.0;
	printf("%lf", result);
	free(val);
}