Layer7 - C언어 4차시 과제

 

이번에는 동아리에서 C언어 마지막 시간이라 그런지 시험을 봤다. 정올 기출문제도 하나 있었는데 나는 시간안에 다 풀었다. 그리고 그 문제들의 풀이글을 블로그에 적는게 과제이다.

 

 

BOJ - 1065

 

https://www.acmicpc.net/problem/1065

1065번: 한수

 

숫자의 각 자리가 등차수열을 이루는지 함수를 정의해서 확인하면 된다. 나는 간단하게 각 자릿수를 분리해서 차가 일정한지 반복문으로 확인하는 식으로 한수를 판별했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool f(int x)
{
	int len = 0, c = 1, sub;
	while (x / c) { len++; c *= 10; }
	if (len == 1)
		return true;
	char* result = (char*)malloc(len+1);
	memset(result, 0, len + 1);
	c /= 10;
	for (int i = 0; i < len; i++)
	{
		result[i] = (x / c);
		x -= (x / c) * c;
		c /= 10;
	}
	sub = result[1] - result[0];
	for (int i = 1; i < len - 1; i++)
	{
		if (result[i + 1] - result[i] != sub)
			return false;
	}
	return true;
}

int main(void)
{
	int n, c = 0;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		if (f(i))
			c++;
	}

	printf("%d", c);

	return 0;
}

 

 

BOJ - 10872

 

https://www.acmicpc.net/problem/10872

10872번: 팩토리얼

 

 

팩토리얼을 구하는 문제이다. 반복문으로도 구현 가능하고 재귀함수로도 간단하게 구현 가능하다. 워낙 간단해서 딱히 할말이 없다.

 

#define _CRT_SECURE_NO_WARNINGS

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

int f(int x) { if (x < 1)return 1; return x * f(x - 1); }

int main(void)
{
	int num = 0;
	scanf("%d", &num);

	printf("%d\n", f(num));

	return 0;
}

 

 

BOJ - 21966

 

https://www.acmicpc.net/problem/21966

21966번: (중략)

 

 

이 문제는 입학식 전에 신입생 특별교육때 주길래 풀었던 문제이다. 포인터 연산 하면서 어거지로 구현했던 기억이 있다. 백준은 브론즈 ~ 실버 정도 문제들은 특정 알고리즘 기법을 적용해야 되는 문제들도 있지만 위 문제와 같이 순수 코딩 능력만으로 시간복잡도 생각 안하고 어거지로 구현해도 풀리는 문제들이 많은것 같다. 조건에 제시된 그대로 구현해주면 된다. S의 길이가 25이하면 그대로 출력하고 그 이상이라면 앞에 11글자, 뒤에 11글자를 제외하고 나머지 부분에 문장을 구분하는 문자인 '.'이 있는지 체크해주면 된다. 어느정도 코딩 능력만 있다면 그냥 문제에서 하라는대로 어거지로 때려 박으면 늦어도 1시간 내로는 풀리는 문제이다.

 

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

int main() {
	int n, count = 0;
	scanf("%d", &n);
	char *str = malloc(n);
	memset(str, 0, n);
	scanf("%s", str);
	char *ptr1 = NULL;
	char *ptr2 = NULL;
	
	if(n <= 25)
		printf("%s", str);
	else{
		ptr1 = str + 11;
		ptr2 = str + n - 11;
		for(int i = 0; i < (int)(ptr2 - ptr1) - 1; i++){
			if(ptr1[i] == '.')
				count++;
		}
		if(!count){
			for(int i = 0; i < 11; i++)
				printf("%c", str[i]);
			printf("...");
			for(int i = 0; i < 11; i++)
				printf("%c", ptr2[i]);
		}
		else{
			for(int i = 0; i < 9; i++)
				printf("%c", str[i]);
			printf("......");
			for(int i = 1; i <= 10; i++)
				printf("%c", ptr2[i]);
		}
	}

	return 0;
}

 

 

BOJ - 14467

 

https://www.acmicpc.net/problem/14467

14467번: 소가 길을 건너간 이유 1

 

 

같은 번호의 소가 위치를 바꾼것이 몇번인지 세면 되는 문제이다. 총 N개의 상태가 입력으로 주어지는데 예를들어서 3 1이면 3번 소가 1의 위치에 있다는 말이다. 위치는 1과 0으로 오직 2가지 상태뿐이다. 1과 0은 각각 왼쪽, 오른쪽을 의미한다고 생각하면 된다. 즉 3 1 -> 3 1이면 3번 소가 이동하지 않은 상태지만 3 1 -> 3 0이면 소가 한번 이동했다고 카운트가 되는것이다. 이 문제 역시 별다른 알고리즘 기법을 몰라도 문제만 제대로 이해하고 어느정도 구현 능력만 있다면 충분히 풀 수 있다. 다른 번호의 소랑도 섞여서 입력이 들어오니까 2중 반복문을 이용해서 1번 소부터 10번 소까지 순서대로 몇번 이동했는지 구해서 더해줬다.

 

#define _CRT_SECURE_NO_WARNINGS

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

int main(void)
{
	int n, count = 0;
	bool street, start = false;
	scanf("%d", &n);
	int* cow = (int *)malloc(n * 4 + 1);
	bool* s = (bool*)malloc(n + 1);

	for (int i = 0; i < n; i++)
	{
		scanf("%d ", &cow[i]);
		scanf("%d", &s[i]);
	}

	for (int i = 1; i <= 10; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!start && cow[j] == i) { start = true;  street = s[j]; }
			else if (s[j] != street && cow[j] == i && start) { street = s[j]; count++; }
		}
		start = false;
	}

	printf("%d", count);

	return 0;
}

 

 

BOJ - 19941

 

https://www.acmicpc.net/problem/19941

19941번: 햄버거 분배

 

이 문제는 2020년 정올에 출제된 문제이다. 알고리즘 분류를 보니까 그리디 알고리즘이길래 생각을 조금 해봤다. 머릿속으로 그림을 그려보니까 앞에서부터 순차적으로 해를 구해나가면 마지막에도 최적의 해가 나오게 된다. 그리디 알고리즘 기초 문제인것 같다. 구현 방식은 일단 햄버거가 위치하는 곳을 true로 표시해두고 P를 만나면 해당 P의 인덱스가 I라고 하면 I - K부터 I + K까지 탐색해서 햄버거가 존재할 경우 해당 위치에는 false로 표시하고 카운트를 증가시키는 방식으로 구현했다.

 

 

#define _CRT_SECURE_NO_WARNINGS

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

int main(void)
{
	int n, k, c = 0;
	scanf("%d %d", &n, &k);
	char* str = (char*)malloc(n + 1);
	bool* check = (bool*)malloc(n + 1);
	memset(check, 0, n + 1);

	scanf("%s", str);

	for (int i = 0; i < n; i++)
		if (str[i] == 'H') check[i] = true;

	for (int i = 0; i < n; i++)
	{
		if (str[i] == 'P')
		{
			for (int j = i - k; j <= i + k; j++)
			{
				if (j < 0 && j >= n) continue;
				else if (str[j] == 'H' && check[j]) { check[j] = false; c++; break; }
			}
		}
	}

	printf("%d", c);

	return 0;
}