굳건하게

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

기존 코드 : https://travelbeeee.tistory.com/297

 기존 코드에서는 무조건 4등분으로 영역을 분할해 나가면서 모든 경우에 대해서 재귀함수를 통해 탐색했습니다. 하지만, 우리는 답이 있는 영역만 탐색해보면 되므로 if 문을 통해 다음과 같이 쓸데없는 탐색을 줄일 수 있습니다.

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

int N, r, c;

void visit(int x, int y, int length, int i) {
	if (length == 2) {
		if (x == r && y == c)
			cout << i;
		else if (x == r && y + 1 == c)
			cout << i + 1;
		else if (x + 1 == r && y == c)
			cout << i + 2;
		else if (x + 1 == r && y + 1 == c)
			cout << i + 3;
		return;
	}

	int j = length / 2;
	if (x <= r && r < x + j && y <= c && c < y + j)
		visit(x, y, j, i);
	else if(x <= r && r < x + j && y + j <= c && c < y + 2 *j)
		visit(x, y + j, j, i + j * j);
	else if(x + j <= r && r < x + 2 * j && y <= c && c < y + j)
		visit(x + j, y, j, i + 2 * j * j);
	else
		visit(x + j, y + j, j, i + 3 * j * j);
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> r >> c;
	int L = int(pow(2, N));
	visit(0, 0, L, 0);
}

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

[ 알고리즘풀이 ]

재귀함수를 이용해 영역을 4등분으로 나눠가면서, 탐색할 영역 시작 좌표, 영역 길이, 시작 인덱스를 넘겨주면 된다.

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

int N, r, c;

void visit(int x, int y, int length, int i) {
	if (length == 1) {
		if (x == r && y == c)
			cout << i;
		return;
	}

	int j = length / 2;
	visit(x, y, j, i);
	visit(x, y + j, j, i + j * j);
	visit(x + j, y, j, i + 2 * j * j);
	visit(x + j, y + j, j, i + 3 * j * j);
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> r >> c;
	int L = int(pow(2, N));
	visit(0, 0, L, 0);
}

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

[ 알고리즘풀이 ]

 에라토스테네스체 + DP 를 이용해서 문제를 해결할 수 있습니다.

1. 에라토스테네스체를 이용해서 100,000 이하의 모든 소수를 check 합니다.

2.  DP[i] : 소인수 분해했을 때 나오는 소수의 개수. 라고 정의

→ i를 나누는 가장 작은 소수 j에 대해서 DP[i] = DP[i / j] + 1 이 성립합니다.

이 방정식을 이용해서 DP 배열을 채울 수 있습니다. 이때, i가 소수면 DP[i] = 1이 되므로, (1) 에라토스테네스체를 채워가는 과정에서 소수에 대해서만 DP[i] = 1로 초깃값을 줍니다. 

3. A ~ B 까지 순회하며 DP 값이 소수인 애들을 count 해줍니다.

#include<iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int A, B, ans = 0, dp[100001] = {};
	bool prime[100001] = {};

	prime[0] = true, prime[1] = true;

	for (int i = 2; i <= 100000; i++) {
		if (prime[i] == false) {
			dp[i] = 1;
			for (int j = 2 * i; j <= 100000; j += i)
				prime[j] = true;
		}
	}

	cin >> A >> B;

	for (int i = 2; i <= B; i++) {
		if (dp[i] == 0) {
			for (int j = 2; ; j++) {
				if (i % j == 0){
					dp[i] = dp[i / j] + 1;
					break;
				}
			}
		}
	}

	for (int i = A; i <= B; i++) {
		if (prime[dp[i]] == false)
			ans++;
	}

	cout << ans;
}

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

[ 알고리즘풀이 ]

1. 톱니바퀴의 상태를 12시부터 시계방향으로 배열에 저장합니다.

( chain[a][b] : a번 톱니바퀴의 12시 시계방향 기준으로 b번 째 톱니 )

2. 입력된 회전 명령에 의해 회전되는 톱니바퀴들을 check 해야합니다.

 direction[ ] 배열을 선언해, i번 톱니바퀴가 회전을 해야 되는지, 해야 한다면 시계방향인지 반시계 방향인지 저장합니다.

 이때, a번 톱니바퀴가 b( 시계방향이면1, 반시계 방향이면 -1)로 회전해야 한다면 (a + 1)번 톱니바퀴는 a번과 맞닿는 부분에 따라서 회전해야 한다면 -b 방향으로 회전해야 합니다.

		// 오른쪽 check.
		for (int i = a; i < 4; i++)
			if (chain[i][2] != chain[i + 1][6])
				direction[i + 1] = -direction[i];
		// 왼쪽 check.
		for (int i = a; i > 1; i--) {
			if (chain[i][6] != chain[i - 1][2])
				direction[i - 1] = -direction[i];
		}

 즉, 다음과 같이 a번 톱니바퀴에서 오른쪽으로 체크, 왼쪽으로 체크해서 direction[ ] 배열을 채워나갈 수 있습니다.

3. direction[ ] 배열을 통해 우리는 몇 번 톱니바퀴를 어떻게 회전해야 되는지 알 수 있으므로, turn 함수를 통해 톱니바퀴를 돌려줍니다.

4. 2~3 과정을 반복해 모든 회전 명령을 다 수행했다면 점수를 계산해주면 됩니다.

#include<iostream>
#include<string>

using namespace std;

int chain[5][8] = {}, t, a, b;
string input;

void turn(int a, int dir) {
	int temp;
	if(dir == 1){
		temp = chain[a][7];
		for (int i = 7; i > 0; i--)
			chain[a][i] = chain[a][i - 1];
		chain[a][0] = temp;
	}
	else {
		temp = chain[a][0];
		for (int i = 0; i < 7; i++)
			chain[a][i] = chain[a][i + 1];
		chain[a][7] = temp;
	}
	return;
}

int getScore(void) {
	int ans = 0, mul = 1;
	for (int i = 1; i <= 4; i++){
		if (chain[i][0] == 1)
			ans += mul;
		mul *= 2;
	}
	return ans;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);


	for (int i = 1; i <= 4; i++) {
		cin >> input;
		for (int j = 0; j < 8; j++)
			chain[i][j] = (input[j] - '0');
	}

	cin >> t;
	while (t--) {
		cin >> a >> b;
		// 1-2 2-3 3-4 톱니바퀴가 회전해야되는지 체크.
		int direction[5] = {};
		direction[a] = b;
		// 오른쪽 check.
		for (int i = a; i < 4; i++)
			if (chain[i][2] != chain[i + 1][6])
				direction[i + 1] = -direction[i];
		// 왼쪽 check.
		for (int i = a; i > 1; i--) {
			if (chain[i][6] != chain[i - 1][2])
				direction[i - 1] = -direction[i];
		}
		for (int i = 1; i < 5; i++) {
			if (direction[i])
				turn(i, direction[i]);
		}
	}
	cout << getScore() << '\n';

	return 0;
}