Having, Doing, and Being

BOJ 2309

7’22”

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

#include <iostream>
using namespace std;
#include <algorithm>
int main() {
	int h[9];
	int sum = 0;
	for (int i = 0; i < 9; i++) {
		cin >> h[i];
		sum += h[i];
	}
	sort(h, h + 9);
	int findTwo = sum - 100;
	int f1, f2; bool find = false;
	for (int i = 0; i < 9; i++) {
		int findOne = findTwo - h[i];
		for (int j = i; j < 9; j++) {
			if (findOne == h[j]) {
				f1 = i; f2 = j; find = true;
				break;
			}
		}
		if (find) break;
	}

	for (int i = 0; i < 9; i++) {
		if (i == f1 || i == f2) continue;
		cout << h[i] << endl;
	}
}

BOJ 2231

27’01”

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

#include <iostream>
using namespace std;
int main() {
	int n;
	cin >> n;

	char str[7]; //max n is 1000000
	int startNum = n - sprintf_s(str, "%d", n) * 9;

	for (int i = startNum; i < n; i++) {
		int k = sprintf_s(str, "%d", i); //digits

		int sum = i;
		for (int j = 0; j < k; j++) {
			sum += str[j] - '0';
		}

		if (sum == n) {
			cout << i;
			return;
		}
	}

	cout << 0;
}

comment

분해합 = 생성자 + 생성자의 자리수의 합

따라서 생성자는 항상 분해합보다 작다.(answer < N )

한편,

생성자 = 분해합 - 생성자의 자리수의 합

이므로 생성자의 최솟값은 분해합 - 생성자의 자리수의 합 이다. 생성자의 자리수의 합의 최대값을 구하면 생성자의 최솟값을 찾을 수 있다.

그런데 생성자의 자리수의 합 은 생성자의 각 자리수가 모두 9 일때 최대값을 갖는다. 또한 생성자는 분해합보다 작으므로,

생성자의 자리수의 합 < 분해합의 자리수 * 9 이다.

따라서 생성자는 항상 분해합 - 분해합의 자리수 * 9 보다 크다. (N - NDigits * 9 < answer)

BOJ 3085

맞왜틀 ㅡㅡ

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

#include <iostream>
#include <algorithm>
using namespace std;

int n;
char arr[50][50];

int findMax() {
	int cnt;
	for (int i = 0; i < n; i++) {
		int tmpRow = 1, tmpCol = 1;
		for (int j = 1; j < n; j++) { //row
			if (arr[i][j] == arr[i][j - 1])
				cnt = max(cnt, ++tmpRow);
			else
				tmpRow = 1;
		}
		for (int j = 1; j < n; j++) { //col
			if (arr[j][i] == arr[j - 1][i])
				cnt = max(cnt, ++tmpCol);
			else
				tmpCol = 1;
		}
	}
	return cnt;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int ans;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < n; j++) {
			//row
			swap(arr[i][j], arr[i][j - 1]);
			ans = max(ans, findMax());
			swap(arr[i][j], arr[i][j - 1]);
			//col
			swap(arr[j - 1][i], arr[j][i]);
			ans = max(ans,findMax());
			swap(arr[j - 1][i], arr[j][i]);
		}
	}

	cout << ans;
}

BOJ 10448

15’33”

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

#include <iostream>
using namespace std;

int main() {
	int tr[46];
	for (int i = 1; i < 46; i++) {
		tr[i] = (i * i + i) / 2;
	}

	int T;
	cin >> T;
	while (T--) {
		int tri = 0;
		int k;
		cin >> k;

		for (int i = 1; tr[i] < k; i++){
			for (int j = 1; tr[j] < k; j++) {
				for (int h = 1; tr[h] < k; h++) {
					if (tr[i] + tr[j] + tr[h] == k) {
						tri = 1;
						break;
					}
				}
				if (tri) break;
			}
			if (tri) break;
		}

		cout << tri << endl;
	}
}

BOJ 2503

38’13”

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

#include <iostream>
#include <string>
using namespace std;

int main() {
	int n;
	cin >> n;

	int arr[1000];
	fill_n(arr, 1000, 1);
	for (int h = 123; h < 999; h++) {
		string tmp = to_string(h);
		if (tmp[0] == tmp[1] || tmp[1] == tmp[2] || tmp[2] == tmp[0]) {
			arr[h] = 0;
		}
		if (tmp[0] == '0' || tmp[1] == '0' || tmp[2] == '0') {
			arr[h] = 0;
		}
	}

	while (n--) {
		int k, s, b;
		cin >> k >> s >> b;
		string str = to_string(k);
		for (int h = 123; h < 999; h++) {
			if (arr[h]) {
				string tmp = to_string(h);
				int tmps = 0, tmpb = 0;
				for (int i = 0; i < 3; i++) {
					for (int j = 0; j < 3; j++) {
						if (str[i] == tmp[j]) {
							if (i == j) tmps++;
							else tmpb++;
						}
					}
				}
				if (tmps != s || tmpb != b)
					arr[h] = 0;
			}
		}

	}

	int ans = 0;
	for (int h = 123; h < 999; h++) {
		if (arr[h]) ans++;
	}
	cout << ans << endl;
}

comment

fill_n(arr, 1000, 1); string str = to_string(k);

BOJ 1018

29’50”

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

#include <iostream>
#include <algorithm>
using namespace std;

char chess[9][8] = {
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B'
};

int main() {
	int n, m;
	cin >> n >> m;
	char arr[50][50];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int min_ans = 64;
	for (int i = 0; i <= n-8; i++) {
		for (int j = 0; j <= m-8; j++) {

			int startRow;
			if (arr[i][j] == 'W') startRow = 0;
			else startRow = 1;

			int tmp = 0;
			for (int r = 0; r < 8; r++) {
				for (int s = 0; s < 8; s++) {
					if (arr[i + r][j + s] != chess[startRow + r][s])
						tmp++;
				}
			}

			tmp = min(tmp, 64 - tmp);
			min_ans = min(min_ans, tmp);
		}
	}

	cout << min_ans << endl;
}

comment

8 8

BBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

를 시도했을 때, 정답은 1이 나와야 한다.

내 코드는 첫 번째 값을 기준으로 체스판의 색을 비교하는 것이지만, 첫 번째 값을 바꾸는 것이 최소 일 수도 있다.

즉 ‘W’ 로 시작하는 체스판이 최소 횟수일지, ‘B’ 로 시작하는 체스판이 최소 횟수일지 알아야 한다. 그러기 위해서는 첫 번째 값을 기준으로 바꿔야 할 갯수를 세고, tmp = min(tmp, 64-tmp) 로 정확한 최솟값을 확인한다.

이 이유는 ‘W’ 로 시작하는 체스판

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

과

‘B’ 로 시작하는 체스판

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

의 동일 위치에 있는 각각의 원소가 반대의 값을 갖기 때문이다.

BOJ 1182

31’19”

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

#include <iostream>
using namespace std;

int n, s;
int arr[20];
int ans = 0;

void find(int idx, int sum) {
	if (n <= idx) return;
	if (arr[idx] == sum) ans++;
	find(idx + 1, sum - arr[idx]);
	find(idx + 1, sum);
}

int main() {
	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	find(0, s);
	cout << ans << endl;
}