무지개 달팽이

Q. JOI시는 남북방향이 H 킬로미터, 동서방향이 W 킬로미터인 직사각형 모양이다. JOI시는 가로와 세로의 길이가 1킬로미터인 H × W 개의 작은 구역들로 나뉘어 있다. 북쪽으로부터 i 번째, 서쪽으로부터 j 번째에 있는 구역을 (i, j) 로 표시한다.

각 구역의 하늘에는 구름이 있을 수도, 없을 수도 있다. 모든 구름은 1분이 지날 때마다 1킬로미터씩 동쪽으로 이동한다. 오늘은 날씨가 정말 좋기 때문에 JOI시의 외부에서 구름이 이동해 오는 경우는 없다.

지금 각 구역의 하늘에 구름이 있는지 없는지를 알고 있다. 기상청에서 일하고 있는 여러분은 각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 예측하는 일을 맡았다.

각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 구하여라.

입력.

입력은 1 + H 행으로 주어진다.

첫 번째 행에는 정수 H, W (1 ≦ H ≦ 100, 1 ≦ W ≦ 100) 가 공백을 사이에 주고 주어진다. 이것은 JOI시가 H × W 개의 작은 구역으로 나뉘어 있다는 것을 의미한다.

이어진 H 개의 행의 i번째 행 (1 ≦ i ≦ H) 에는 W문자의 문자열이 주어진다. W 개의 문자 중 j번째 문자 (1 ≦ j ≦ W) 는, 구역 (i, j) 에 지금 구름이 떠 있는지 아닌지를 나타낸다. 구름이 있는 경우에는 영어 소문자 'c' 가, 구름이 없는 경우에는 문자 '.' 가 주어진다.

출력.

출력은 H 행으로, 각 행에는 공백으로 구분된 W 개의 정수를 출력한다. 출력의 i 번째 행 j 번째 정수 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 는, 지금부터 몇 분후에 처음으로 구역 (i, j) 에 구름이 뜨는지를 표시한다. 단, 처음부터 구역 (i, j) 에 구름이 떠 있었던 경우에는 0을, 몇 분이 지나도 구름이 뜨지 않을 경우에는 -1을 출력한다.

아래와 같은 방법으로 문제를 해결했다.

" 각 행에 'c'가 있는 경우 0에서 시작해 다음 'c'가 올 때까지 숫자를 증가 "

" 'c'가 없는 경우 해당 행에 대해 -1을 출력"

자료형이 string이 아닌, char형 배열에서도 행의 마지막에 널 문자가 들어간다는 것을 알게 되었다.

#include <stdio.h>
#include <stdbool.h>

int main(void) {
	int i, j, h, w;
	int ans;
	char land[100][101];

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

	for (i = 0; i < h; i++)
		for (j = 0; j <= w; j++)
			scanf("%c", &land[i][j]);

	bool b = false;

	for (i = 0; i < h; i++) {
		ans = -1; b = false;

		for (j = 0; j < w; j++) {
			if (b)
				ans++;

			if (land[i][j] == 'c') {
				ans = 0;
				b = true;
			}

			printf("%d ", ans);
		}
		putchar('\n');
	}

	return 0;
}

Q. 자연수 n개가 주어진다. 이 자연수의 공약수를 모두 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 n이 주어진다. n은 2 또는 3이다. 둘째 줄에는 공약수를 구해야 하는 자연수 n개가 주어진다. 모든 자연수는 108 이하이다.

출력.

입력으로 주어진 n개 수의 공약수를 한 줄에 하나씩 증가하는 순서대로 출력한다.

처음에는 해결법을 다음과 같이 생각했다.

1. 입력받은 숫자를 소수로 나누고 그 횟수의 최솟값을 구한다.

2. 나누었던 소수와 그 횟수를 통해 나올 수 있는 수들을 오름차순으로 출력한다.

그런데 여기서는 두 번째 방식을 구현하는데 반복문을 사용하기 까다로워 어려움을 겪었다.

그러나 아래의 방식을 사용하면 간단히 문제를 해결할 수 있다.

" 1 ~ 입력받은 숫자 중 가장 작은 수를 나누어 공통적으로 나머지가 0인 숫자를 출력 "

#include <stdio.h>

int main(void) {
	int i, min, n;
	int arr[3] = {0, 0, 0};

	scanf("%d", &n);

	scanf("%d", &arr[0]);
	min = arr[0];

	if (n == 2) 
		scanf("%d", &arr[1]);
	else
		scanf("%d %d", &arr[1], &arr[2]);

	for (i = 1; i < n; i++)
		if (arr[i] < min)
			min = arr[i];

	for (i = 1; i <= min; i++)
		if (arr[0] % i == 0 && arr[1] % i == 0 && arr[2] % i == 0)
			printf("%d\n", i);
	
	return 0;
}

Q. 상근이와 친구들은 MT에 가서 아래 설명과 같이 재미있는 게임을 할 것이다.

각 플레이어는 1이상 100 이하의 정수를 카드에 적어 제출한다. 각 플레이어는 자신과 같은 수를 쓴 사람이 없다면, 자신이 쓴 수와 같은 점수를 얻는다. 만약, 같은 수를 쓴 다른 사람이 있는 경우에는 점수를 얻을 수 없다.

상근이와 친구들은 이 게임을 3번 했다. 각 플레이어가 각각 쓴 수가 주어졌을 때, 3번 게임에서 얻은 총 점수를 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 참가자의 수 N이 주어진다. (2 ≤ N ≤ 200) 둘째 줄부터 N개 줄에는 각 플레이어가 1번째, 2번째, 3번째 게임에서 쓴 수가 공백으로 구분되어 주어진다.

출력.

각 플레이어가 3번의 게임에서 얻은 총 점수를 입력으로 주어진 순서대로 출력한다.

이차원 배열의 요소의 값을 같은 행에 해당하는 요소의 값과 하나씩 비교하는 방법을 사용했다.

비교한 결과, 값은 값이 있으면 0으로 바꾸어 주었다.

그리고 이 문제에서는 컴파일 에러가 발생했는데, 주로 헤더 파일에 문제가 있을 때 나타난다고 한다.

알아보니 C언어는 bool 자료형이 없다는 것을 알게 되었고, 아래의 두 가지 방법으로 문제를 해결하였다.

C언어에는 bool 자료형이 없기 때문에 1을 true, 0을 false로 지정해서 한다. 다음은 C언어에서 bool 자료형을 사용하는 방법이다.

#include <stdio.h>
#include <stdbool.h>

int main(void) {
	int i, j, k, n;
	bool check;
	int input[200][3];
	int score[200];

	scanf("%d", &n);

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

	for (i = 0; i < 3; i++) {	
		for (j = 0; j < n; j++) {
			check = false;

			for (k = j + 1; k < n; k++) {
				if (input[j][i] == input[k][i]) {
					input[k][i] = 0;
					check = true;
				}
			}

			if (check)
				input[j][i] = 0;
		}
	}

	for (i = 0; i < n; i++) {
		score[i] = input[i][0] + input[i][1] + input[i][2];
		printf("%d\n", score[i]);
	}

	return 0;
}

#include <stdio.h>

int main(void) {
	int i, j, k, n;
	_Bool check;
	int input[200][3];
	int score[200];

	scanf("%d", &n);

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

	for (i = 0; i < 3; i++) {	
		for (j = 0; j < n; j++) {
			check = 0;

			for (k = j + 1; k < n; k++) {
				if (input[j][i] == input[k][i]) {
					input[k][i] = 0;
					check = 1;
				}
			}

			if (check)
				input[j][i] = 0;
		}
	}

	for (i = 0; i < n; i++) {
		score[i] = input[i][0] + input[i][1] + input[i][2];
		printf("%d\n", score[i]);
	}

	return 0;
}

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