무지개 달팽이

Q. 세 정수 A, B, C가 주어진다. 이때, 두 번째로 큰 정수를 출력하는 프로그램을 작성하시오. 

입력.

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

출력.

두 번째로 큰 정수를 출력한다.

함수 형식 매크로를 이용해서 간단하게 값을 바꾸는 방식을 사용했다. (여기서 오류가 났다.)

사용해야 하는 값이 3개 뿐이므로 하나하나 비교하였다.

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

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

int main(void) {
	int i;
	int tmp[3];

	scanf("%d", &tmp[0]);

	for (i = 1; i < 3; i++) {
		scanf("%d", &tmp[i]);

		if (tmp[i] < tmp[i-1])
			swap(int, tmp[i], tmp[i-1]);
	}

	if (tmp[0] > tmp[1])
		swap(int, tmp[0], tmp[1]);

	printf("%d", tmp[1]);
	
	return 0;
}

Q. ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 여러분은 지우를 도와 줄 프로그램을 작성하고자 한다. 즉 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다.

문제를 단순화하기 위해서 호텔은 직사각형 모양이라고 가정하자. 각 층에 W 개의 방이 있는 H 층 건물이라고 가정하자 (1 ≤ H, W ≤ 99). 그리고 엘리베이터는 가장 왼쪽에 있다고 가정하자(그림 1 참고). 이런 형태의 호텔을 H × W 형태 호텔이라고 부른다. 호텔 정문은 일층 엘리베이터 바로 앞에 있는데, 정문에서 엘리베이터까지의 거리는 무시한다. 또 모든 인접한 두 방 사이의 거리는 같은 거리(거리 1)라고 가정하고 호텔의 정면 쪽에만 방이 있다고 가정한다.

그림 1. H = 6 이고 W = 12 인 H × W 호텔을 간략하게 나타낸 그림

방 번호는 YXX 나 YYXX 형태인데 여기서 Y 나 YY 는 층 수를 나타내고 XX 는 엘리베이터에서부터 세었을 때의 번호를 나타낸다. 즉, 그림 1 에서 빗금으로 표시한 방은 305 호가 된다.

손님은 엘리베이터를 타고 이동하는 거리는 신경 쓰지 않는다. 다만 걷는 거리가 같을 때에는 아래층의 방을 더 선호한다. 예를 들면 102 호 방보다는 301 호 방을 더 선호하는데, 102 호는 거리 2 만큼 걸어야 하지만 301 호는 거리 1 만큼만 걸으면 되기 때문이다. 같은 이유로 102 호보다 2101 호를 더 선호한다.

여러분이 작성할 프로그램은 초기에 모든 방이 비어있다고 가정하에 이 정책에 따라 N 번째로 도착한 손님에게 배정될 방 번호를 계산하는 프로그램이다. 첫 번째 손님은 101 호, 두 번째 손님은 201 호 등과 같이 배정한다. 그림 1 의 경우를 예로 들면, H = 6이므로 10 번째 손님은 402 호에 배정해야 한다.

입력.

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수를 포함하고 있으며 각각 호텔의 층 수, 각 층의 방 수, 몇 번째 손님인지를 나타낸다(1 ≤ H, W ≤ 99, 1 ≤ N ≤ H × W). 

출력.

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행을 출력하는데, 내용은 N 번째 손님에게 배정되어야 하는 방 번호를 출력한다.

이 문제에서 고려해야 할 것은 " 정문에서 가까운 순 " 으로 방을 배정하는 것이다. 이때 거리가 같다면 " 아래층 순 " 으로 배정한다.

그러므로 층 수를 우선 계산하는데 최대 높이인 h 보다 입력값인 n 이 크면, h 값을 빼고 호 수 변수인 x 를 +1 해준다.

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

typedef struct {
	int x;
	int y;
} Case;

void Print(int x, int y)
{
	printf("%d", y);

	if(x>=10)
		printf("%d", x);
	else
		printf("0%d",x);

	putchar('\n');
}

int main(void)
{
	int i, t, h, w, n;
	int x, y;
	Case *ans;

	scanf("%d", &t);

	ans = (Case*)calloc(t, sizeof(Case));

	for (i = t - 1; i >= 0; i--) {
		x = 1, y = 1;

		scanf("%d %d %d", &h, &w, &n);

		while (n > h) {
			n -= h;
			x++;
		}
		
		y = n;

		ans[i].x = x; ans[i].y = y;
	}

	for (i = t - 1; i >= 0; i--)
		Print(ans[i].x, ans[i].y);

	return 0;
}

Q. 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다.

예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다.

노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고 한다.

A, B, C가 주어졌을 때, 손익분기점을 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 21억 이하의 자연수이다.

출력.

첫 번째 줄에 손익분기점 즉 최초로 이익이 발생하는 판매량을 출력한다. 손익분기점이 존재하지 않으면 -1을 출력한다.

우선 -1이 출력되는 경우는 판매비용(C)가 가변비용(B)보다 작거나 같은 경우이다. 이 경우는 고정비용이 더해지기 때문에 총 수입이 더 많아질 수 없기 때문이다.

문제를 직관적으로 살펴보면, A + ( B * x ) < C * x 라는 식을 유추해낼 수 있다. ( x : 노트북 개수 )

즉 A < x * ( C - B )와 같은 표현이다. 이 조건이 성립할 때까지 x를 증가시키는 알고리즘을 생각했다.

그러나 시간 초과가 났고, 그 이유는 x가 증가할 때마다 x * ( C - B ) 이 부분을 계속 해야했기 때문이다.

그러므로 이 문제는 아래와 같이 해결해주면 된다.

"A / ( C - B ) < x 이 되는 x 값을 찾으면 된다."

#include <stdio.h>

int main(void)
{
	int a, b, c;
	int ans = 1;
	int tmp;

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

	tmp = a / (c-b);

	if (b < c) {
		while(1) {
			if(tmp < ans)
				break;

			ans++;
		}

		printf("%d", ans);
	}
	else
		printf("%d", -1);

	return 0;
}

Q. 평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

입력.

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 <= k <= 14, 1 <= n <= 14)

출력.

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

입력할 수 있는 값의 범위가 작기 때문에 2호는 +1, 3호는 + (3 + (1 * 층수)) ˙˙˙ 이런 식으로 진행하면 될 것이라고 생각했다. 그런데 4호부터는 이 규칙이 적용되지 않았다.

"이 문제는 (k - 1층 n호) + (k층 n - 1호) 의 인원 수를 더하면 구할 수 있다."

또, 확실하게 인원 수를 알 수 있는 것은 (1) 0층이거나, (2) 1호인 경우 이다. 그렇기 때문에 재귀 함수를 사용한다.

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

int Person(int a, int b)
{
	if (a == 0)
		return b;
	if (b == 1)
		return 1;

	return Person(a-1, b) + Person(a, b-1);
}

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

	scanf("%d", &t);

	ans = (int*)calloc(t, sizeof(int));

	for (i = 0; i < t; i++) {
		scanf("%d", &k); scanf("%d", &n);

		ans[i] = Person(k, n);
	}

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

	return 0;
}

Q. 무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력.

첫째 줄에 분수를 출력한다.

"해당하는 레벨 구하기 + 그 레벨에서 몇 번 째 분수인지 구하기"

표를 트리 모양으로 바꿔서 생각해보면, 

홀수번 째 레벨 : 분자 감소, 분모 증가  /  짝수번 째 레벨 : 분자 증가, 분모 감소

위와 같은 규칙을 발견할 수 있다.

그리고 입력받은 수의 레벨이 몇 번 째인지 알아내기 위해, x을 대입한 변수 tmp에 변수 cnt의 값을 빼주면서 cnt > tmp가 되는 구간을 찾아낸다. 이 반복문을 끝냈을 때 나온 변수 tmp의 값은 해당 레벨에서 몇 번 째 분수인지 알아내는데 사용한다.

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

int main(void)
{
	int x;			

	int i, tmp, cnt;	

	int child, parent;

	scanf("%d", &x);

	if (x == 1)
		printf("1/1");
	else {

		cnt = 1;

		tmp = x;

		while (tmp > cnt)
		{
			tmp -= cnt;
			cnt++;
		}

		if (cnt % 2 == 0)
		{
			parent = cnt; child = 1;

			for (i = 1; i < tmp; i++)
			{
				parent--;
				child++;
			}
		}
		else
		{
			parent = 1; child = cnt;

			for (i = 1; i < tmp; i++)
			{
				parent++;
				child--;
			}
		}

		printf("%d/%d", child, parent);
	}

	return 0;
}

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