무지개 달팽이

Q. 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력.

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

이분 탐색 관련 문제를 풀어보고 싶어서 선택한 문제이다.

현재까지 공부한 바로는 이분 탐색을 하기 위해서는 기준 배열이 나오는 것으로 알고 있는데, 이 문제에서는 찾을 수 없었다. 그래서 여러 블로그에서 문제 풀이를 살펴 보았다.

"( 나무의 길이(v) - 낮에 올라가는 거리(a) ) 에서 하루에 올라가는 거리(a - b)를 나누고

나누어 떨어지면 그 몫을 날 수(n)에 더하고, 떨어지지 않으면 여기에 +1을 하여 더한다."

즉, 이분 탐색으로 풀기 보다 수학 문제처럼 접근하는 것이 좋다는 것이다.

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

int main(void)
{
	int v, a, b;
	int n = 1;

	scanf("%d", &a); scanf("%d", &b); scanf("%d", &v);

	int temp = (v - a) / (a - b);

	if ((v - a) % (a - b) == 0)
		n += temp;
	else
		n += (temp + 1);

	printf("%d", n);

	return 0;
}

Q. 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력.

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

기본적인 이진 탐색 문제이다. 

그러므로 아래와 같은 방법으로 문제를 해결해주면 된다.

"숫자 카드를 정렬(오름차순) + 정수 하나씩 탐색"

처음에는 단순 선택 정렬을 선택했는데 시간 초과가 났다. 그래서 퀵 정렬(qsort 함수 이용)로 바꿨을 때 문제를 해결한 것을 보고, 알고리즘에서 단순히 문제를 해결하는 것보다 효율적으로 해결하는 것이 중요하다는 것을 깨달았다.

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

int bin_search(const int a[], int n, int key)
{
	int pl = 0;
	int pr = n - 1;
	int pc;

	do {
		pc = (pl + pr) / 2;
		
		if (a[pc] == key)
			return 1;
		else if (a[pc] < key)
			pl = pc + 1;
		else
			pr = pc - 1;
	} while(pl <= pr);

	return 0;
}

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;
	int n, m;
	int *num;
	int *card;

	scanf("%d", &n);
	
	num = (int*)calloc(n, sizeof(int));

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

	card = (int*)calloc(m, sizeof(int));

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

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

	for (i = 0; i < m; i++)
	{
		printf("%d ", bin_search(num, n, card[i]));
	}

	free(num); free(card);

	return 0;
}

Q. N마리의 새가 나무에 앉아있고, 자연수를 배우기 원한다. 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 어떤 숫자 K를 노래할 때, K마리의 새가 나무에서 하늘을 향해 날아간다. 만약, 현재 나무에 앉아있는 새의 수가 지금 불러야 하는 수 보다 작을 때는, 1부터 게임을 다시 시작한다.

나무에 앉아 있는 새의 수 N이 주어질 때, 하나의 수를 노래하는데 1이 걸린다고 하면, 모든 새가 날아가기까지 총 몇 초가 걸리는지 출력하는 프로그램을 작성하시오.

입력. 

첫째 줄에 새의 수 N이 주어진다. 이 값은 10^9보다 작거나 같다.

출력.

첫째 줄에 정답을 출력한다.

문제를 이해하는데 어려움이 있었다. 결국은 불러야 하는 자연수보다 남은 새의 수가 작을 때만 고려하면 쉬운 문제였다.

"숫자만큼 (새의 수) 를 빼기 + 시간 카운팅"

이것을 중심으로 만약 (새의 수) < 자연수 이면, 숫자를 1로 변경하는 반복문만 이용하면 된다.

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

int main(void)
{
	int i;
	int n, count;

	scanf("%d", &n);

	count = 0;

	while (n > 0)
	{
		for (i = 1; i <= n; i++)
		{
			count++;
			n -= i;
		}
	}

	printf("%d", count);

	return 0;
}