[열혈 C] 도전! 프로그래밍1 - 유클리드 호제법과 덧셈조합

 오늘은 열혈 C의 도전! 프로그래밍 1 파트를 풀어보겠습니다. 교재에 답이 없기 때문에 제가 틀렸을 수도 있습니다. 이점 유의하고 봐주시기 바랍니다. 도전 1부터 도전 8까지 있는데 제가 풀면서 고민했던 문제만 풀이해 보겠습니다!

 

도전 3 두 개의 정수를 입력 받아서 최대 공약수(GCD)를 구하는 프로그램을 작성 해 보자.

 이 문제는 풀이가 두가지 입니다. 첫 번째 방법인 단순하게 후보들을 전부 나눠보는 방법부터 설명하겠습니다.

#include<stdio.h>
int main(void) {
	int min, max;
	int a, b;
	int gcd=1;
	scanf_s("%d %d", &a, &b);
	min = a > b ? b : a;    //작은 수로 초기화
	max = a > b ? a : b;    //큰 수로 초기화
	for (int i = 1;i < min + 1;i++)
		if (min % i == 0 && max % i == 0)    //작은 수와 큰 수로 나누어 떨어지는 i의 최댓값 구하기
			gcd = i;
	printf("%d", gcd);
}

19332 78696 36

 두번째 방법은 유클리드 호제법을 이용하는 방법입니다. 유클리드 호제법이 궁금하신 분들은 링크를 클릭하여 보시기 바랍니다.

#include<stdio.h>
int main(void) {
	int min, max;
	int a, b;
	int gcd=1;
	scanf_s("%d %d", &a, &b);
	min = a > b ? b : a;
	max = a > b ? a : b;
	int remainder;    //나머지 정의
	while (1) {
		remainder = max % min;    //큰 수를 작은 수로 나눈 나머지
		if (remainder == 0)    //나머지가 0이 되면 탈출
		{
			gcd = min;
			break;
		}
		max = min;
		min = remainder;
	}
	printf("%d", gcd);
}

19332 78696 36

 

도전 4 필자가 좋아하는 것 중 하나가 금요일 저녁 퇴근길에 DVD나 만화책을 잔뜩 빌리고, 동네 슈퍼에 들려서 군것질거리를 사가지고 집에 들어가는 것이다. 오늘은 금요일이다. 현재 필자의 주머니에는 5천원이 있다. DVD 한편을 빌리면 3,500원이 남는다. 슈퍼에 들려서 크림빵(500원), 새우깡(700원), 콜라(400원)를 사려한다. 잔돈을 하나도 남기지 않고 이 세가지 물건을 하나 이상 반드시 구매하려면 어떻게 구매를 진행해야 하겠는가? 물론 여기에는 여러가지 경우의 수가 있을것이다. 필자가 어떠한 선택을 할 수 있는지 여러분이 제시해 주기 바란다.

 어떻게 조합을 알아내야 할까 고민하다가 모든 경우의 수를 다 조사해 보는 방법을 선택했습니다.

#include<stdio.h>
int main(void) {
	int money = 3500;    //가진돈
	int snack = 700, scnt = 0;    //새우깡 가격, 구매한 새우깡의 수
	int bread = 500, bcnt = 0;    //크림빵 가격, 구매한 크림빵의 수
	int coke = 400, ccnt = 0;    //콜라 가격, 구매한 콜라의 수
	for (scnt = 1;scnt < 4;scnt++)    //3500원에서 크림빵과 콜라가격을 빼면 새우깡을 최대 3개 살 수 있다.
	{
		for (bcnt = 1;bcnt < 5;bcnt++)    //3500원에서 새우깡과 콜라가격을 빼면 크림빵을 최대 4개 살 수 있다.
		{
			for (ccnt = 1;ccnt < 6;ccnt++)    //3500원에서 새우깡과 크림빵가격을 빼면 콜라를 최대 5개 살 수 있다.
				if (money - scnt * snack - bcnt * bread - ccnt * coke == 0)    //모든 물품을 샀을때 잔돈이 0원이 되어야 한다.
					printf("새우깡 %d개 크림빵 %d개 콜라 %d개\n", scnt, bcnt, ccnt);
		}
	}
}

새우깡 1개 크림빵 4개 콜라 2개 새우깡 2개 크림빵 1개 콜라 4개 새우깡 3개 크림빵 2개 콜라 1개