무지개 달팽이

Q. 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어의 점수는 레벨을 클리어하면서 얻은 점수의 합으로, 이 점수를 바탕으로 온라인 순위를 매긴다. 동준이는 레벨을 난이도 순으로 배치했다. 하지만, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만들었다.

이 문제를 해결하기 위해 동준이는 특정 레벨의 점수를 감소시키려고 한다. 이렇게해서 각 레벨을 클리어할 때 주는 점수가 증가하게 만들려고 한다.

각 레벨을 클리어할 때 얻는 점수가 주어졌을 때, 몇 번 감소시키면 되는지 구하는 프로그램을 작성하시오. 점수는 항상 양수이어야 하고, 1만큼 감소시키는 것이 1번이다. 항상 답이 존재하는 경우만 주어진다. 정답이 여러 가지인 경우에는 점수를 내리는 것을 최소한으로 하는 방법을 찾아야 한다.

입력.

첫째 줄에 레벨의 수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개 줄에는 각 레벨을 클리어하면 얻는 점수가 첫 번째 레벨부터 마지막 레벨까지 순서대로 주어진다. 점수는 20,000보다 작은 양의 정수이다.

출력.

첫째 줄에 점수를 몇 번 감소시키면 되는지 출력한다.

레벨이 올라갈수록 받을 수 있는 점수도 커지도록, 입력받은 수를 수정하는 문제이다.

즉, 중요한 것은 낮은 레벨의 점수가 높은 레벨의 점수보다 무조건 작아야 한다는 것이다.

문제에서 점수는 항상 양수이고, 항상 답이 존재한다고 하였으니까 arr[i] <= i + 1 인 경우는 없다.

그러므로 점수 배열 ( arr ) 에서 arr[i] > arr[i+1] 이 TRUE인 경우에만,

arr[i] 와 arr[i + 1] - 1의 차만큼 답에 더해주고, arr[i]의 값을 arr[i + 1] - 1으로 교체해주는 반복문을 만들어 준다.

#include <stdio.h>

int MAX(int a, int b)
{
    int max;

    if (a >= b)
        max = a;
    else
        max = b;
    
    return max;
}

int main(void)
{
    int n, ans = 0;

    scanf("%d", &n);
    
    int arr[n];

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

    for (int i = n - 2; i > -1; i--)
    {   

        if (arr[i] >= arr[i+1]) {

            ans += arr[i] - (arr[i+1]-1);

            arr[i] = arr[i+1]-1;
        }

    }

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

    return 0;
}

Q. N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력.

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다.

출력.

첫째 줄에 줄을 선 순서대로 키를 출력한다.

배열에 값이 있는지 체크하기 위해, 숫자가 저장되는 배열을 0으로 초기화시켜주고 시작한다.

이 문제는 두 개의 반복문을 사용하여 문제를 해결하였다.

1. 큰 수가 들어갈 수 있는 빈 공간을 남겨두는 것이 요점이므로, 빈 공간을 체크하는 반복문

2. 만약 조건을 만족한 자리에 다른 수가 있을 경우에 뒷 자리에 위치하게 하는 반복문

#include <stdio.h>

int main(void) {
	int i, j, n, cnt;
	int arr[10] = {0,};

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		int tmp;

		scanf("%d", &tmp);
		
		j = 0; cnt = 0;

		while(cnt != tmp) 
			if (arr[j++] == 0) cnt++;

		while (arr[j] != 0)
			j++;

		arr[j] = i + 1;

	}

	for (i = 0; i < n; i++)
		printf("%d ", arr[i]);

	return 0;
}

Q. 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

입력.

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력.

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

연속된 숫자들을 묶었을 때, 0의 묶음과 1의 묶음 중 작은 것을 출력하면 된다. 

#include <stdio.h>

int main(void) {
	int i, nOne, nZero;
	char arr[1000001];

	i = 0;
	nOne = 0; nZero = 0;

	while(1) {
		scanf("%c", &arr[i]);
		
		if (arr[i++] == '\n')
			break;
	}

	i = 0;

	while(1) {
		if (arr[i] == '0') {
			while (arr[i+1] == '0')
				i++;
			nZero += 1;
			i++;
		}
		else {
			while (arr[i+1] == '1')
				i++;
			nOne += 1;
			i++;
		}
		
		if (arr[i] == '\n')
			break;
	}

	if (nZero < nOne)
		printf("%d\n", nZero);
	else
		printf("%d\n", nOne);

	return 0;
}

Q. 한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력.

첫째 줄에 센서의 개수 N(1<=N<=10,000), 둘째 줄에 집중국의 개수 K(1<=K<=1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 이상 있으며, 좌표의 절댓값은 1,000,000 이하이다.

출력.

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

이 문제는 크게 k 개의 범위로 센서들을 모두 묶는 것과 같다고 할 수 있다. 즉, 아래와 같은 방법으로 문제를 해결했다.

" 센서 사이의 거리가 큰 순서로 k - 1개를 총 센서 사이의 거리에서 뺌. "

우선 고속도로 위의 센서들을 시각화하기 위해 입력받은 센서들의 위치를 정렬한다.

정렬을 한 후, 이웃한 센서 사이의 구하여 배열 ( arr_cmp )로 만들어 정렬한다. 마지막으로 이 배열의 인덱스 0 ~ k - 2를 갖는 요소를 총 센서 사이의 거리에서 빼준다. 

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

int int_cmp(const int *a, const int *b)
{
	if (*a < *b)
		return 1;
	else if (*a > *b)
		return -1;
	else
		return 0;
}

int main(void) {
	int i, n, k, ans;
	int *arr, *arr_cmp;

	scanf("%d", &n); scanf("%d", &k);

	arr = (int*)calloc(n, sizeof(int));

	arr_cmp = (int*)calloc(n - 1, sizeof(int));

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

	qsort(arr, n, sizeof(int), (int(*)(const void *, const void *))int_cmp);

	for (i = 0; i < n - 1; i++) {
		if (arr[i] != arr[i + 1])
			arr_cmp[i] = (arr[i] - arr[i + 1]);
	}

	qsort(arr_cmp, n - 1, sizeof(int), (int(*)(const void *, const void *))int_cmp);;
	
	ans = 0;

	for (i = 0; i < k - 1; i++) 
		ans += arr_cmp[i];

	if (n <= k)
		printf("%d\n", 0);
	else
		printf("%d\n", (arr[0] - arr[n-1]) - ans);

	free(arr); free(arr_cmp);

	return 0;
}

Q. 월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러도 랭킹이 높은 사람이 반드시 이기게 된다. 따라서 월드시에서는 게임을 흥미진진하게 만들기 위해서, 부전승을 여러 번 만들더라도 각 시합에 임하는 선수들의 랭킹 차이를 비슷하게 만들려고 한다.

토너먼트를 만들 때에는 이미 추첨이 된 순서대로 선수들을 배치하고, 왼쪽에서 오른쪽의 순서가 어긋나지 않도록 시합을 정한다. 물론 부전승을 임의로 만들 수 있지만, 토너먼트가 꼬여서는 안 된다. 또한, 각 시합에 임하는 두 선수의 랭킹의 차이의 합이 최소가 되도록 하려 한다.

예를 들어 추첨 결과가 차례로 랭킹 1, 6, 2, 5, 3, 4위의 선수들이었을 때의 토너먼트 세 개가 위에 있다. <A>의 경우는 각 시합이 (1 6), (2 5), (3 4), (1 2), (1 3)으로 랭킹 차이의 합이 5+3+1+1+2=12가 된다. 반면에 <B>는 11이, <C>는 10이 된다.

토너먼트 추첨 결과가 주어졌을 때, 각 시합에 임하는 두 선수의 랭킹 차이의 총 합의 최솟값을 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 자연수 n(1≤n≤256)이 주어진다. 다음 줄에는 추첨 결과를 나타내는 n명의 선수들의 랭킹이 주어진다. 각 선수의 랭킹은 1부터 n까지의 자연수로 나타나며, 랭킹이 같은 경우는 없다고 가정하자.

출력.

첫째 줄에 답을 출력한다.

" 현재 배열에서 가장 큰 값 찾기 + 찾은 값의 왼, 오른 쪽에 있는 값 중 더 큰 값 찾기 "

두 선수의 랭킹 차이를 최소로 하기 위해서 두 랭킹값의 차이가 가장 작도록 해야하므로, 위와 같은 방식의 반복문을 사용하였다. 이 반복문을 한 번 돌 때마다 증가하는 변수 i 를 이용하여 배열의 인덱스 값을 조절하였다. 

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

int main(void) {
	int i, j, n, ans = 0;
	int *arr;

	scanf("%d", &n);

	arr = (int*)calloc(n, sizeof(int));

	for (i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	int max, idx;

	for (i = 0; i < n - 1; i++) {
		int tmp = n - i;

		max = 0;

		for (j = 0; j < tmp; j++) {
			if (max < arr[j]) {
				max = arr[j];
				idx = j;
			}
		}

		int n_idx;	// 배열의 최댓값 기준 양 옆에서 더 큰 수

		if (0 < idx && idx < tmp - 1)
			n_idx = (arr[idx + 1] >= arr[idx - 1]) ? arr[idx + 1] : arr[idx - 1];
		else if (idx == 0)
			n_idx = arr[idx + 1];
		else
			n_idx = arr[idx - 1];

		ans += (max - n_idx);

		for (int m_idx = idx + 1; m_idx < tmp; m_idx++)
			arr[m_idx - 1] = arr[m_idx];
	}

	printf("%d", ans);

	free(arr);

	return 0;
}