[백준]1074 집합

jyukki included in 백준

2020-03-04 156 words One minute

Contents

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

풀이:

배열의 크기를 점차 줄여가면서,

위에 방문할 수 있는 배열의 크기를 계산하여, 더해가면서 구한다.

ex)

3 7 7

8 * 8 배열에서

왼쪽위, 오른쪽 위, 왼쪽 아래 4 * 4 배열은 필요없으니까 48 만큼 뺀 후,

오른쪽 아래 배열로만 4 * 4 배열로 줄여서 다시 만든다.

그렇다면, ( 7, 7 ) 은 ( 3, 3 )이 되어야 하므로 (7 % 4, 7 % 4) 가 된다.

배열의 크기가 0이 될때까지 반복한다.

코드:

사용언어 : c++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


#include <iostream>
using namespace std;
int n, r, c, a = 0;
int main() {
	cin >> n >> r >> c;
	n = (1 << (n - 1));
	while (n) {
		a += r / n * n * n * 2 + c / n * n * n;
		r %= n;
		c %= n;
		n /= 2;
	}
	cout << a << endl;
}