끝이 없을 모험 이야기

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

bool compare(string a, string b)
{
	if (a.length() == b.length())
		return a<b;
	else return a.length() < b.length();
}

int main()
{
	int n;
	cin >> n;
	string* alist = new string[n];

	for (int i = 0; i < n; i++)
	{
		cin >> alist[i];
	}
	sort(alist, alist+n, compare);

	for (int i = 0; i < n; i++)
	{
		if (i>0 && alist[i] == alist[i - 1])
			continue;
		cout << alist[i] << endl;
	}

	delete[] alist;
	return 0;
}

문제: https://www.acmicpc.net/problem/1181

#include <iostream>

using namespace std;

int cut(int x) 
{
	int stick = 64;
	int shortStick = 64;
	int n = 1;
	while (x < stick) 
	{
		shortStick = shortStick/2;
		if (x <= (stick - shortStick))
		{
			stick -= shortStick;
			n--;
		}
		n++;
	}
	return n;
}

int main()
{
	int x;
	cin >> x;
	cout << cut(x);
}

문제: https://www.acmicpc.net/problem/1094

#include <iostream>
using namespace std;

class Stack
{
public:
	Stack(int k)
	{ 
		this->length = k;
		this->top = -1;
		this->arr = new int[length];
	}
	~Stack()
	{
		delete[] arr;
	}
	void insert(int n)
	{
		top++;
		arr[top] = n;
	}
	bool isEmpty()
	{
		if (top == -1)
			return 1;
		else
			return 0;
	}
	int size()
	{
		return top + 1;
	}
	int pop()
	{
		if (top == -1)
			return -1;
		else
		{
			top--;
			return arr[top + 1];
		}
	}
	int getTop()
	{
		if (top == -1)
			return -1;
		else
		{
			return arr[top];
		}
	}


private:
	int length;
	int top;
	int* arr;
};

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, command, num;
	cin >> n;
	Stack Mystack = Stack(n - 1);
	for (int i = 0; i < n; i++)
	{
		cin >> command;
		switch (command)
		{
		case 1:
			cin >> num;
			Mystack.insert(num);
			break;
		case 2:
			cout << Mystack.pop() << '\n';
			break;
		case 3:
			cout << Mystack.size() << '\n';
			break;
		case 4:
			cout << Mystack.isEmpty() << '\n';
			break;
		case 5:
			if (Mystack.isEmpty())
				cout << -1 << '\n';
			else
			{
				cout << Mystack.getTop() << '\n';
			}
			break;
		}
	}
}

첫 시도 때 시간초과가 떠서 아래의 코드를 메인 함수에 넣어줬다. 두 줄로 바로 해결되었다.

ios_base::sync_with_stdio(false);
cin.tie(NULL);

문제에서의 입력의 양이 많기 때문에 빠른 입출력 방식을 사용해야 했다.

문제: https://www.acmicpc.net/problem/28278

#include <iostream>
#include <string>

using namespace std;

int count(int n, int m, char* board[]) {
	int num = 2500;
	int num1 = 0;
	int num2 = 0;
	int result=2500;

	for (int a = 0; a < n - 7; a++) {
		for (int b = 0; b < m - 7; b++) {
			num1 = 0;
			num2 = 0;
			for (int i = a; i < 8 + a; i++) {
				for (int j = b; j < 8 + b; j++) {
						if ((i + j - a - b) % 2 == 0) {
							if (board[i][j] == 'B') {
								num1++;
							}
							else
								num2++;
						}
						else {
							if (board[i][j] == 'W')
								num1++;
							else
								num2++;
						}
				}
			}
			num = num1 > num2 ? num2 : num1;
			if (result > num)
				result = num;
			//cout << num1 << " " << num2 << " " << result << endl;
		}
	}

	return result;
}

int main() {
	int n, m, result;
	cin >> n >> m;
	char** board = new char * [n];

	for (int i = 0; i < n; i++) {
		board[i] = new char[m];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}


	result = count(n, m, board);

	cout << result;


	for (int i = 0; i < n; i++)
		delete[] board[i];

	delete[] board;
}

체스판을 무조건 8x8로 잘라낸다는 조건과 W으로 시작할 지, B으로 시작할 지에 집중했다.

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

#include <iostream>

using namespace std;

int main() {
	int num, a;
	unsigned long long b, result;
	cin >> num;

	for (int i = 0; i < num; i++) {
		cin >> a >> b;
		result = a;
		if (b == 1) {
			result = result % 10;
			if (result == 0)
				result = 10;
		}
		else {
			for (int j = 0; j < b - 1; j++) {
				result = (result * a) % 10;
				if (result == 0) {
					result = 10;
					break;
				}
			}
		}
		cout << result << '\n';
	}
	return 0;
}

문제를 해석해 보면 결국 첫째 자리 숫자가 무엇인지가 궁금한 것이다.

문제: https://www.acmicpc.net/problem/1009

#include <iostream>

using namespace std;

void find(int a, int b, int arr[52][52]) {
	try {
		if (arr[a + 1][b] == 100) {
			arr[a + 1][b]++;
			find(a + 1, b, arr);
		}
		if (arr[a - 1][b] == 100) {
			arr[a - 1][b]++;
			find(a - 1, b, arr);
		}
		if (arr[a][b + 1] == 100) {
			arr[a][b + 1]++;
			find(a, b + 1, arr);
		}

		if (arr[a][b - 1] == 100) {
			arr[a][b - 1]++;
			find(a, b - 1, arr);
		}
	} 
	catch (exception) {

	}
}
int main() {
	int num, m, n, k, x, y, count;
	
	cin >> num;

	for (int i = 0; i < num; i++) {
		count = 0;
		cin >> m >> n >> k;
		// reset ground
		int ground[52][52] = {0,};

		for (int j = 0; j < k; j++) {
			cin >> x >> y;
			ground[y][x] = 100;
		}
		// find
		for (int a = 0; a < n; a++) {
			for (int b = 0; b < m; b++) {
				if (ground[a][b] == 100) {
					ground[a][b]++;
					count++;
					find(a, b, ground);
				}
			}
		}
		cout << count << '\n';

	}
	return 0;
}

재귀함수를 쓰는 것이 포인트인 것 같다.

문제: https://www.acmicpc.net/problem/1012

#include <iostream>

using namespace std;

int main() {
	int n, m, num, k;
	long long result;
	cin >> num;

	for (int i = 0; i < num; i++) {
		result = 1;
		k = 1;
		cin >> n >> m;
		for (int j = 0; j < n; j++) {
			result = result*m/k;
			k++;
			m--;
		} 
		cout << result << '\n';
	}
	return 0;
}

조합의 특성을 생각해보면 쉽게 풀 수 있다.

문제: https://www.acmicpc.net/problem/1010

#include <iostream>

using namespace std;

class Fibonacci {
	int a = 0;
	int b = 0;
public:
	Fibonacci() {}
	int fibonacci(int n) {
		if (n == 0) {
			count_a();
			return 0;
		}
		else if (n == 1) {
			count_b();
			return 1;
		}
		else {
			return fibonacci(n - 1) + fibonacci(n - 2);
		}
	}
	void count_a() {
		a++;
	}
	void count_b() {
		b++;
	}
	int get_a() {
		return a;
	}
	int get_b() {
		return b;
	}
	void reset_a() {
		a = 0;
	}
	void reset_b() {
		b = 0;
	}
	~Fibonacci() {}
};

int main(){
	Fibonacci fi = Fibonacci();
	int n, k;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> k;
		fi.fibonacci(k);
		cout << fi.get_a() << " " << fi.get_b() << endl;
		fi.reset_a();
		fi.reset_b();
	}
	return 0;
}

다음과 같이 풀고자 했으나 시간 초과가 떴다.

이유를 찾아보니 재귀함수를 사용하여 이미 fibonacci(3)을 구한 적이 있지만 또 다시 구하는 상황이 발생해서이다.

따라서 다이나믹 프로그래밍 기법을 사용했다. 아래와 같다.

#include <iostream>

using namespace std;
void fibonacci(int k, int save[40][3])
{
	save[0][0] = 0;
	save[0][1] = 1;
	save[0][2] = 0;
	save[1][0] = 1;
	save[1][1] = 0;
	save[1][2] = 1;
	for (int i = 2; i <= k; i++) {
		save[i][0] = save[i - 1][0] + save[i - 2][0];
		save[i][1] = save[i - 1][1] + save[i - 2][1];
		save[i][2] = save[i - 1][2] + save[i - 2][2];
	}
}
int main(){
	int n, k;
	int save[40][3];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> k;
		if (k == 0) {
			cout << 1 << " " << 0 << '\n';
			continue;
		}
		else if (k == 1) {
			cout << 0 << " " << 1 << '\n';
			continue;
		}
		fibonacci(k, save);
		cout << save[k][1] << " " << save[k][2] << '\n';
	}
	return 0;
}

문제: https://www.acmicpc.net/problem/1003

#include <iostream>
#include <cmath>

using namespace std;
int main(){
	int n, x1, x2, y1, y2, r1, r2, result;
	bool in = true;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
		if (x1 == x2 && y1 == y2 && r1 == r2) {
			result = -1;
		}
		else if (sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2)) > r1 + r2)
			result = 0;
		else if (sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2)) == r1 + r2)
			result = 1;
		else if (sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2)) == abs(r1 - r2))
			result = 1;
		else if (sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2)) < abs(r1 - r2))
			result = 0;
		else
			result = 2;
		cout << result << endl;
		in = true;
	}
	return 0;
}

원을 두 개 그려서 '어떻게', '어디서' 만나는지의 여부를 따져보면 된다.

문제:https://www.acmicpc.net/problem/1002

#include <iostream>
#include <algorithm>

using namespace std;
int main(){
	int result[100][100] = {0};
	int n, a, b;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		for(int j=0; j<10; j++)
			for(int k=0; k<10; k++)
				result[a + j][b + k] = 1;
	}
	cout << count(&result[0][0], &result[0][0]+10000, 1);
	return 0;
}

흰도화지(0)인 100x100 2차원 array를 만들어 검은 색종이(1)가 붙여진 위치에 값을 1로 수정해준다는 아이디어.

문제: https://www.acmicpc.net/problem/2563

#include <iostream>
#include <string>

using namespace std;
int main() {
	string s[5];
	string result="";

	cin >> s[0] >> s[1] >> s[2] >> s[3] >> s[4];
	
	int max = 0;
	for (int i = 0; i < 5; i++)
	{
		if (max < s[i].length())
			max = s[i].length();
	}
	for (int i = 0; i < max; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			try
			{
				result += s[j].substr(i, 1);
			}
			catch (exception e)
			{
				continue;
			}
		}
	}
	cout << result;
}

문제: https://www.acmicpc.net/problem/10798

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

int main() {
	int arr[9][9];
	int max = 0, col, row;

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (arr[i][j] >= max) {
				max = arr[i][j];
				col = i+1;
				row = j+1;
			}
		}
	}

	cout << max << '\n' << col << " " << row;
	
	return 0;
}

두번째 for문의 if문에서 최댓값이 0일 수 있으므로 >=로 해줘야 한다.

문제: https://www.acmicpc.net/problem/2566