[알고리즘 공부 7일차]

1. 블랙잭

카드의 갯수,목표 숫자,카드의 숫자를 받고 가장 목표의 가까운값을 찾는 문제이다 카드의 숫자를 배열로 만들어 앞에서부터 3개씩 골라 더해 그 차이가 가장 적을때를 저장해서 출력해주면된다

	num = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &num[i]);
	}
	min = m;
	for (int i = 0; i < n - 2; i++)
	{
		for (int j = i + 1; j < n - 1; j++)
		{
			for (int k = j + 1; k < n; k++)
			{
				temp = num[i] + num[j] + num[k];
				if ((temp <= m) && (m - temp <= min))
				{
					min = m - temp;
					key = temp;
				}
			}
		}
	}

2.분해합

숫자 a를 받은뒤 숫자 a의 가장 작은 생성자를 구한다.
반복문을 통해 1부터 분해합을 구한뒤 a와같다면 출력해주면된다.
분해합은 정수 i라고 할때 i를 더한뒤 i가 > 0 클때가지 10으로 나눈 나머지를 더하면된다

for (int i = 1; i < a; i++)
	{
		num = i;
		temp = i;
		while (temp > 0)
		{
			num += temp % 10;
			temp = temp / 10;
		}
		if (num == a)
		{
			key = i;
			break;
		}
	}

3.덩치

정수 a를 입력받은뒤 a크기의 배열 3개를 동적할당한다. l,w,ans 배열에에는 각각 몸무게 키 등수가 들어간다 m배열을 1로 초기화한뒤
비교를 시작한다 2중반복문을 통해 자기자신을 제외한 인자들과 비교를한후 자신보다 덩치가 큰 (키도 몸무게도 큰) 인자가있다면 해당하는 등수르 1늘려준다.

l = (int*)malloc(sizeof(int) * a);
	w = (int*)malloc(sizeof(int) * a);
	ans = (int*)malloc(sizeof(int) * a);
	for (int i = 0; i < a; i++)
	{
		scanf("%d %d", &l[i], &w[i]);
		ans[i] = 1;
	}
	for (int i = 0; i < a; i++)
	{
		for (int j = 0; j < a; j++)
		{
			if (i == j)
				continue;
			if (l[i] < l[j])
				if (w[i] < w[j])
					ans[i]++;
		}
	}

4.체스판 다시 칠하기

NxM을 입력으로 받고 8X8로 분할하여 몇개를 고쳐야하는지 비교하는식으로 문제를 해결했다.

우선 N과M을 입력받은뒤 반복문을통해 BW를 입력받는다 여기서 편의성을위
해 B일때는 1 W일때는 0으로 NM크기의 int배열을 초기화해준다

다음 비교를위해 정답 보드 두개를 만든다 8*8 2차원배열로 B로 시작하는 경우 와 W로 시작하는경우 두개를 초기화 해서 만들면된다.

다음 입력받은 NM배열을 정답배열과 비교한후 다를때마다 카운트를 증가시켜 가장 최솟값이 나올때를 찾으면 정답이다.

int main()
{
	int a, b, cnt,cnt2, ans;
	int** check;
	char c;
	int board1[8][8];
	int board2[8][8];


	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			board1[i][j] = (i + j) % 2;
			board2[i][j] = (i + j + 1) % 2;
		}
	}

	cin >> a >> b;
	ans = a * b;

	check = (int**)malloc(sizeof(int*) * a);
	for (int i = 0; i < a; i++)
	{
		check[i] = (int*)malloc(sizeof(int) * b);
		for (int j = 0; j < b; j++)
		{
			cin >> c;
			{
				if (c == 'B')
					check[i][j] = 1;
				else if (c == 'W')
					check[i][j] = 0;
			}
		}
	}
	
	for (int i = 0; i + 8 <= a; i++)
	{
		for (int j = 0; j + 8 <= b; j++)
		{
			cnt = 0;
			cnt2 = 0;
			for (int k = 0; k < 8; k++)
			{
				for (int l = 0; l < 8; l++)
				{
					if (check[i + k][j + l] != board1[k][l])
						cnt++;
					if (check[i + k][j + l] != board2[k][l])
						cnt2++;
				}
			}
			ans = min(ans,min(cnt,cnt2));
		}
	}
	printf("%d ", ans);
}

6.영화 감독 숌

666부터 1씩증가시키면서 666이 연속적으로 나오는경우를 카운트해서 원하는 값에서 멈춘후 출력하면된다 666이 연속적으로 나오는것을 판별하는것은 10으로 나눈 나머지가 6일때 cnt6를 증가시키고 아니라면 0으로 초기화한다 이때 cnt6이 3이라면 세번연속으로 나온경우이므로 cnt를 증가후 break를통해 탈출하면된다.

#include <iostream>

using namespace std;
int main(void)
{
	int temp,i = 666,a, cnt=0,cnt6;
	cin >> a;

	while (1)
	{
		cnt6= 0;
		temp = i;
		while (temp > 0)
		{
			if (temp % 10 == 6)
			{
				cnt6++;
			}
			else
			{
				cnt6 = 0;
			}
			if (cnt6 == 3)
			{
				cnt++;
				break;
			}
			temp /= 10;
		}
		if (a == cnt)
		{
			cout << i;
			break;
		}
		i++;
	}
}