무지개 달팽이

Q. 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0]*B[0] + ... + A[N-1]*B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

입력.

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력.

첫째 줄에 S의 최솟값을 출력한다.

( 배열 A의 요소 ) X ( 배열 B의 요소 ) 의 형태로 만들어 그 합의 최솟값을 구하는 문제이다. 

이 문제는 아래와 같은 두 가지 방식으로 접근했다.

※ 정렬은 버블정렬을 이용하였다.

①

문제에는 배열 B는 재배열 하지 않는다는 조건이 있지만, 단순히 문제를 해결하기 위해서는 다음과 같은 방법을 사용할 수 있다.

배열 B의 요소값은 큰 순서대로 배열 A의 요소값이 작은 순서대로 정렬

+

후에 곱하여 모두 더함

즉, 정렬 알고리즘만을 이용하여 해결한 경우이다.

#include <stdio.h>

#define swap(type, x, y) do{type t = x; x = y; y = t;} while(0)

void a_bubble (int a[], int n) {
	int i, j;

	for (i = 0; i < n - 1; i++)
		for (j = n - 1; j > i; j--)
			if (a[j - 1] > a[j])
				swap(int, a[j - 1], a[j]);
}

void b_bubble(int a[], int n) {
	int i, j;

	for (i = 0; i < n - 1; i++)
		for (j = n - 1; j > i; j--)
			if (a[j - 1] < a[j])
				swap(int, a[j - 1], a[j]);
}

int main(void) {
	int i, n, ans = 0;
	int a[50], b[50];

	scanf("%d", &n);
	
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);
	
	for (i = 0; i < n; i++)
		scanf("%d", &b[i]);

	a_bubble(a, n);
	b_bubble(b, n);
	
	while (n--) 
		ans += (a[n]*b[n]);

	printf("%d\n", ans);
	
	return 0;
}

Q. 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

입력.

첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.

출력.

첫째 줄에 그룹 단어의 개수를 출력한다.

순서대로 사용한 알파벳에는 방문 체크를 해두었다가, 다음 방문 시 체크 여부를 확인하여

방문 한 경우 변수 N 값을 감소하면서 총 그룹 단어 개수를 구하였다.

방문 여부는 배열 alpha를 이용하였다.

#include <stdio.h>
#include <string.h>

int main(void) {
	int i, n, ans, tmp;
	char word[101];
	
	scanf("%d", &n);

	ans = 0;
	
	int cnt = n;

	while(cnt--) {
		scanf("%s", word);

		tmp = word[0] % 97;

		int alpha[26] = {0,};

		for (i = 1; i < strlen(word); i++) {
			if (tmp != word[i] % 97) {
				if (alpha[word[i] % 97] != 0) {
					n--;
					break;
				}
				else {
					alpha[tmp] = 1;
					tmp = word[i] % 97;
				}
			}
		}
	}

	printf("%d\n", n);

	return 0;
}