취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5956번 문제인 Symmetry이다.
문제는 아래 링크를 확인하자.

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

소 배치를 한 단계 진행할 때마다 새로운 구역의 크기는 N/2 x M/2(나눗셈의 몫)가 됨을 관찰하자.

또한 새로운 단계를 진행하려면 각 단계의 구역의 변의 길이는 각각 홀수여야됨을 관찰하자.

마지막으로 각 단계를 진행할 때마다 가운데 새로 놓는 소 한마리를 빼고 생각할 때 이전 단계의 패턴이 네 귀퉁이에 들어가 총 소의 마릿수가 4배가 됨을 관찰하면 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int R, C; cin >> R >> C;
	ll ans = 0;
	while ((R & 1) && (C & 1)) {
		ans = ans * 4 + 1;
		R >>= 1, C >>= 1;
	}

	cout << ans;
}