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 자료형을 사용하는 방법이다.

 

1. stdbool.h 라는 헤더파일을 추가한다.

ex)
#include <stdbool.h>

bool b;
b = true;
2. bool 이 아닌, _Bool 을 자료형으로 선언한다.

ex)
_Bool b;

b = 1;

 


 

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

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 10709번  (0) 2020.05.14
[C언어] 5618번  (0) 2020.05.13
[C언어] 10817번  (0) 2020.04.25
[C언어] 10250번  (0) 2020.04.17
[C언어] 1712번  (0) 2020.04.15

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

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 5618번  (0) 2020.05.13
[C언어] 5533번  (0) 2020.05.12
[C언어] 10250번  (0) 2020.04.17
[C언어] 1712번  (0) 2020.04.15
[C언어] 2775번  (0) 2020.04.14

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

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 5533번  (0) 2020.05.12
[C언어] 10817번  (0) 2020.04.25
[C언어] 1712번  (0) 2020.04.15
[C언어] 2775번  (0) 2020.04.14
[C언어] 1193번  (0) 2020.04.13

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

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 10817번  (0) 2020.04.25
[C언어] 10250번  (0) 2020.04.17
[C언어] 2775번  (0) 2020.04.14
[C언어] 1193번  (0) 2020.04.13
[C언어] 2292번  (0) 2020.04.11

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

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 10250번  (0) 2020.04.17
[C언어] 1712번  (0) 2020.04.15
[C언어] 1193번  (0) 2020.04.13
[C언어] 2292번  (0) 2020.04.11
[C언어] 2872번  (0) 2020.04.11

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

 

1/1 1/2 1/3 1/4 1/5 ···
2/1 2/2 2/3 2/4 ··· ···
3/1 3/2 3/3 ··· ··· ···
4/1 4/2 ··· ··· ··· ···
5/1 ··· ··· ··· ··· ···
··· ··· ··· ··· ··· ···

 

이와 같이 나열된 분수들을 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;
}

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 1712번  (0) 2020.04.15
[C언어] 2775번  (0) 2020.04.14
[C언어] 2292번  (0) 2020.04.11
[C언어] 2872번  (0) 2020.04.11
[C언어] 1920번  (0) 2020.04.05

Q.

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

 

입력.

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

 

출력.

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

 


 

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

 

지나가는 방의 개수 1 2 3 · · ·
해당되는 방 번호 1 2 ~ 7 8 ~ 19 · · ·

 

즉, 방 번호의 범위는 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;
}

 

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 2775번  (0) 2020.04.14
[C언어] 1193번  (0) 2020.04.13
[C언어] 2872번  (0) 2020.04.11
[C언어] 1920번  (0) 2020.04.05
[C언어] 2869번  (0) 2020.04.05

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

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 1193번  (0) 2020.04.13
[C언어] 2292번  (0) 2020.04.11
[C언어] 1920번  (0) 2020.04.05
[C언어] 2869번  (0) 2020.04.05
[C언어] 10815번  (0) 2020.04.04

+ Recent posts