무지개 달팽이

Q.

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

입력.

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

출력.

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

이 문제의 규칙은 다음과 같다.

즉, 방 번호의 범위는 1, 6, 12, 18, · · ·이 된다.

이 범위는 한 패스 당 + 6을 하여 정할 수 있다. 이렇게 정한 범위가 입력받은 방 번호(n)보다 클 때 반복을 멈추고, 출력해준다.

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

int main(void)
{
	int n;

	int cnt = 1;
	int range = 1;
	int tmp = 1;

	scanf("%d", &n);

	while(range < n)
	{
		tmp = 6 * cnt;
		range += tmp;
		cnt++;
	}

	printf("%d", cnt);

	return 0;
}

Q. 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다.

오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근이는 책을 알파벳 순서대로 정렬하려고 한다. 사전 순으로 가장 앞서는 책은 가장 위에 놓고, 가장 뒤에 있는 책은 가장 밑에 놓아야 한다. 책을 정렬할 때 사용할 수 있는 방법은 책 하나를 뺀 다음, 가장 위에 놓는 것이다.

책은 1부터 N까지 번호가 책 이름의 사전 순으로 매겨져 있다. 1은 사전 순으로 가장 앞서는 책이다. 따라서, 위에서부터 책의 번호를 읽으면 (1, 2, ..., N)이 되어야 한다. 예를 들어, 책이 3권있고 처음에 (3, 2, 1)로 쌓여있을 때, 2번 만에 사전순으로 책을 쌓을 수 있다. 가장 먼저, 2번 책을 뺀 다음에 가장 위에 놓는다. 그렇게 되면 (2, 3, 1)이 된다. 마지막으로, 1을 뺀 다음 가장 위에 놓으면 (1, 2, 3)이 된다.

현재 책이 어떻게 쌓여있는지가 주어졌을 때, 몇 번만에 사전 순으로 쌓을 수 있는지 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 책의 개수 N이 주어진다. (N ≤ 300,000)

다음 N개 줄에는 가장 위에 있는 책부터 아래에 있는 책까지 순서대로 주어진다.

출력.

첫째 줄에 몇 번만에 책을 정렬할 수 있는지 출력한다.

처음에는 단순히 오름차순으로 정렬을 한다는 생각에 버블 정렬을 이용하여 문제를 해결하려고 하였다. 그런데 시간 초과가 났고, 더 간단한 방법이 있을 것 같았다.

여러 블로그에 올라온 솔루션들을 확인해본 결과, 실제로 정렬을 하는 연산이 필요한 것이 아니라 책의 이동횟수만 구하면 된다는 사실을 알게 되었다. (※ 참고 블로그 : Murra Blog)

"제자리에 있으면 패스 + 없으면 답(이동횟수) + 1"

결국 이것을 포인트하는 문제이다.

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

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

	scanf("%d", &n);

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

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

	int checkNum = n;

	for (i = n - 1; i >= 0; i--)
	{
		if (book[i] == checkNum)
			checkNum--;
		else
			ans++;
	}

	printf("%d", ans);

	free(book);

	return 0;
}

Q. N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력.

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력.

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

10815번과 동일한 문제이다. 단순히 출력 형식만 바꾸어 주면 된다.

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

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

	do {
		int pc = (pl + pr) / 2;

		if (a[pc] > key)
			pr = pc - 1;
		else if (a[pc] < key)
			pl = pc + 1;
		else
			return 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 *a, *b;

	scanf("%d", &n);

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

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

	scanf("%d", &m);

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

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

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

	for (i = 0; i < m; i++)
		printf("%d\n", bin_search(a, n, b[i]));

	return 0;
}

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