무지개 달팽이

Q.

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력.

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력.

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

이 문제는 아래와 같은 방식을 중심으로 배열을 재정리하였다.

" 삼각형 꼭대기의 값은 그대로 두고

아래로 내려오면서 대각선에 위치한 두 값 중 더 큰 것을 해당 값에 더한 결과로 변경 "

여기서 행에서 제일 앞과 뒤의 값은 따로 조건을 주어서 예외 상황을 해결하였다.

그리고 마지막 행일 경우에는 변수 ans를 이용하여 최댓값을 찾도록 하였다.

#include <stdio.h>

int main(void) {
	int i, j, n, ans;
	int dp[500][501] = {0,};

	scanf("%d", &n);

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

	ans = 0;
	for (i = 1; i < n; i++) {
		for (j = 0; j <= i; j++) {
			if (j == 0)
				dp[i][j] += dp[i-1][j];
			else if (j == i)
				dp[i][j] += dp[i-1][j-1];
			else 
				dp[i][j] += (dp[i-1][j-1] >= dp[i-1][j] ? dp[i-1][j-1] : dp[i-1][j]);
	
			if (i == n - 1)
				if (ans < dp[i][j])
					ans = dp[i][j];
		}
	}
	
	printf("%d\n", ans);

	return 0;
}

Q. 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력.

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력.

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

n 값 별로 그림을 그려보았을 때, 블록의 마지막은 길이가 1이 남거나 2가 남는다는 것을 알 수 있다.

그리고 길이 2의 경우에는 2 X 1 블록과, 2 X 2 블록이 올 수 있으므로 다음과 같은 식을 구할 수 있다.

dp[n] = dp[n - 1] + dp[n - 2] * 2

여기서 n의 값이 커질 수록 배열에 들어가는 값도 상당히 증가할 수 있으니,

int형 범위를 넘지 않도록 배열에 값을 넣어줄 때 10,007로 나눈 나머지를 그 값으로 해주었다.

#include <stdio.h>

int main(void) {
	int i, n, dp[1001];

	scanf("%d", &n);

	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 3;

	for (i = 3; i <= n; i++)
		dp[i] = (dp[i-1] + dp[i-2] * 2) % 10007;

	printf("%d\n", dp[n]);

	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. 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력.

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

규칙에 맞춰서 생각을 해보면 dp[n] = dp[i-1] + dp[i-2] + dp[i-3] 이라는 식을 유추해낼 수 있다.

dp 배열에 0, 1, 2의 값을 부여하지 않는 코드를 짤 때는 n이 음수로 될 경우에 값이 0이 되도록 해야할 것이다.

#include <stdio.h>

int main(void) {
	int i, n, tmp, dp[11];

	scanf("%d", &n);

	while (n--) {
		scanf("%d", &tmp);

		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 2;

		for (i = 3; i <= tmp; i++)
			dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

		printf("%d\n", dp[tmp]);
	}

	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;
}

Q. 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력.

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력.

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

이 문제는 아래와 같은 방법을 사용하여 해결할 수 있다.

" 문자열 b와 문자열 a의 차이가 가장 작을 때의 값을 찾는다. "

위와 같은 방법이 가능한 이유는 다음과 같다.

문제를 살펴보면, 문자열 a의 앞, 뒤에 새로운 문자를 추가할 수 있다고 한다. 즉 이것은 문자열 b와 동일한 문자를 추가할 수 있다는 뜻이므로, 기존의 문자열에서 차이의 최솟값을 구하라는 것을 의미한다고 볼 수 있다.

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

int main(void) {
	int i, j;
	char a[51], b[51];

	scanf("%s %s", &a, &b);

	int min = strlen(b);

	for (i = 0; i <= strlen(b) - strlen(a); i++) {
		int tmp = 0, cnt = 0;

		for (j = i ; j < i + strlen(a); j++) {
			if (a[cnt] != b[j])
				tmp++;

			cnt++;
		}
		
		if (min > tmp)
			min = tmp;
	}

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

	return 0;
}