저그유저의 프로그래밍

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

문제를 간단하게 보면

1. 가중치가 있는 양방향 그래프를 입력 받습니다.

 ex) (예제 입력의 가중치 부분입니다.)

1 2 3
2 3 2
2 4 4

2. 시작 버텍스에서 k 가중치 이상인 곳만 탐색을 하고 갯수를 세면 됩니다.

 탐색은 DFS (Depth First Search : Stack)

             BFS (Breadth First Search : Queue)

둘 중에 어느 것을 사용하여도 상관없기에 재귀함수를 이용한 스택 방식으로 구현하였습니다.

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

vector<vector<pair<int, int>>> v;
vector<bool> visited;
int result;

void CheckLink(int k, int from)
{
	result++; //탐색마다 1씩 증가 시켜줍니다.
	visited[from] = true; //같은 인덱스 탐색을 막아줍니다.
	
	int size = v[from].size();

	for (int i = 0; i < size; ++i)
	{
		pair<int, int> p = v[from][i];
		int next = p.first;
		int cost = p.second;

		//이미 방문 되었거나 k보다 작은 곳은 갈 수 없습니다.
		if (visited[next] || cost < k)
		{
			continue;
		}

		//계속 탐색합니다.
		CheckLink(k, next);
	}
}

int main()
{
	int n, Q;
	int p, q, r;
	int k, from;

	scanf("%d %d", &n, &Q);

	v.resize(n + 1); //인덱스가 [1] ~ [n] 까지 시작하여 n + 1 만큼 사용합니다.
	visited.resize(n + 1, false);

	for (int i = 1; i < n; ++i) //n - 1개 입력이기에 i = 1부터 시작합니다.
	{
		scanf("%d %d %d", &p, &q, &r);

		//양방향 그래프이기에 서로 경로, 가중치 를 저장해줍니다.
		v[p].push_back(make_pair(q, r));
		v[q].push_back(make_pair(p, r));
	}

	for (int i = 0; i < Q; ++i)
	{
		scanf("%d %d", &k, &from);

		result = -1;

		//visited 배열을 false로 초기화 시켜줍니다.
		fill(visited.begin(), visited.end(), false);

		//DFS
		CheckLink(k, from);

		printf("%d\n", result);
	}
}

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

물(.) 옆에 있는 빙판(X)은 하루가 지날 때 마다 사라집니다.

백조(L) 두 마리가 며칠 뒤에 만날 수 있는가를 탐색하는 문제입니다.

제가 한 풀이는 이렇습니다. 우선 분리 집합을 통해 그룹화 시켜주었습니다.

( 분리 집합(Disjoint Set) 을 잘 모르시는 분은 나중에 다시 글을 올려 링크해 두겠습니다. )

1. 모든 지형을 탐색합니다. 물이나 백조인 곳을 기점으로 번호를 매겨 DFS 탐색을 해줍니다.

2.  .이라면 계속 탐색하고, X를 만나면 탐색을 중지하고 큐에 넣어줍니다.

3. 백조 두 마리가 처음부터 같은 그룹에 있을 수 있습니다. 이를 확인하여 처리해 줍니다.

4.

 4-1. X 위치에서 주변을 탐색하고 분리 집합 (parent)을 사용하여 같은 그룹으로 만들어 줍니다.

 4-2. bird[0] 과 bird[1] 이 같으면 백조는 서로 만나게 된 상태입니다.

      만났다면 day를 출력

      만나지 못했다면 day를 1 증가 시키고 4-3으로 갑니다.

 4-3. 다시 주변 X를 queue에 넣어주며 4를 반복합니다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

queue<pair<int, int>> q;
vector<int> bird;
vector<int> parent;

char input[1500][1501];
int visited[1500][1500];
int dir[4][2] = 
{
	{1, 0},
	{0, 1},
	{-1, 0},
	{0, -1}
};

void DFS(int startRow, int startCol, int r, int c, int group)
{
	if (input[startRow][startCol] == 'L')
	{
		bird.push_back(group); //새가 어느 그룹에 속해있는지 저장해둡니다.
	}

	for (int i = 0; i < 4; ++i)
	{
		int nextRow = startRow + dir[i][0];
		int nextCol = startCol + dir[i][1];

		if (nextRow < 0 || r <= nextRow ||
			nextCol < 0 || c <= nextCol ||
			visited[nextRow][nextCol] > 0)
		{
			continue;
		}
		
		visited[nextRow][nextCol] = group;

		if (input[nextRow][nextCol] == 'X')
		{
			q.push(make_pair(nextRow, nextCol));
		}
		else
		{
			DFS(nextRow, nextCol, r, c, group);
		}
	}
}

int GetParent(int p)
{
	if (parent[p] == p)
	{
		return p;
	}

	return parent[p] = GetParent(parent[p]);
}

int SetParent(int from, int to)
{
	return parent[from] = parent[to];
}

//테스트 출력용
void PrintState(int r, int c, int day)
{
	cout << endl << "day : " << day << endl;

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			cout << GetParent(visited[i][j]) << "";
		}
		cout << endl;
	}

	cout << "parent : " << endl;

	for (int i = 1; i < parent.size(); ++i)
	{
		cout << "[" << i << "] " << parent[i] << " ";
	}

	cout << endl;
}

int main()
{
	int r, c;
	int day = 1;
	int groupId = 1;
	cin >> r >> c;

	parent.push_back(0);
	for (int i = 0; i < r; ++i)
	{
		cin >> input[i];
	}

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (visited[i][j] > 0)
			{
				continue;
			}

			if (input[i][j] == '.' || input[i][j] == 'L') //탐색 및 그룹화
			{
				visited[i][j] = groupId;
				DFS(i, j, r, c, groupId);
				parent.push_back(groupId);
				groupId++;
			}
		}
	}

	if (GetParent(bird[0]) == GetParent(bird[1])) //이미 만나 있는 상태
	{
		cout << 0 << endl;
		return 0;
	}

	while (!q.empty())
	{
		int size = q.size();

		//4-1
		for (int i = 0; i < size; ++i)
		{
			q.push(q.front());

			int row = q.front().first;
			int col = q.front().second;
			int group = GetParent(visited[row][col]);
			q.pop();

			for (int j = 0; j < 4; ++j)
			{
				int nextRow = row + dir[j][0];
				int nextCol = col + dir[j][1];

				if (nextRow < 0 || r <= nextRow ||
					nextCol < 0 || c <= nextCol || 
					visited[nextRow][nextCol] == 0)
				{
					continue;
				}
				int from = GetParent(visited[nextRow][nextCol]);

				SetParent(from, group);
			}
		}

		//4-2
		PrintState(r, c, day);
		if (GetParent(bird[0]) == GetParent(bird[1]))
		{
			break;
		}
		
		//4-3
		day++;
		for (int i = 0; i < size; ++i)
		{
			int row = q.front().first;
			int col = q.front().second;
			int group = visited[row][col];
			q.pop();

			for (int j = 0; j < 4; ++j)
			{
				int nextRow = row + dir[j][0];
				int nextCol = col + dir[j][1];

				if (nextRow < 0 || r <= nextRow ||
					nextCol < 0 || c <= nextCol ||
					visited[nextRow][nextCol] > 0)
				{
					continue;
				}

				visited[nextRow][nextCol] = group;
				q.push(make_pair(nextRow, nextCol));
			}
		}
	}

	cout << day << endl;
}

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

n개의 나무 중 m개 이상을 가져갈 수 있는 최소 높이를 구하는 문제입니다.

이분 탐색을 이용한 풀이와 높이를 비교하며 푸는 방법 두 가지가 있습니다.

먼저 이분 탐색을 사용한 일반적인 풀이입니다.

(이분 탐색이 left <= right,  left < right 등과 같이 여러 변형이 있고 쓰이는 곳이 달라집니다.

이건 종이에 써가면서 해보는게 좋을거 같네요!)

#include <iostream>
#include <algorithm>

using namespace std;

int input[1000000];

int BinarySearch(int n, int m)
{
	int left = 0;
	int right = 1000000000;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		long long sum = 0LL;

		for (int i = 0; i < n; ++i)
		{
			if (input[i] > mid)
			{
				sum += (long long)input[i] - (long long)mid;
			}
		}

		if (sum == m)
		{
			return mid;
		}
		else if (sum > m)
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}

	return right;
}

int main()
{
	int n, m;
	int left = 0;
	int right = 0;

	cin.tie(0);
	cin >> n >> m;

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

	sort(input, input + n);

	cout << BinarySearch(n, m) << endl;
}

다른 방법은 높이를 큰 순서로 나열한 후 잘라가며 원하는 수량을 체크하는 것입니다.

이 방법은 제가 알아낸 것은 아니고 어떤 분의 풀이였던 것 같습니다.

#include <iostream>
#include <algorithm>

using namespace std;

int input[1000001];

bool compare(int a, int b)
{
	return a > b;
}

int main()
{
	int n, m;
	long long sum = 0;
	int index = 1;
	int cut = 0;

	cin >> n >> m;

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

	sort(input, input + n, compare);

	while (sum < m)
	{
		sum += ( (long long)input[index - 1] - (long long)input[index] ) * index;
		index++;
	}

	cut = (sum - m) / (index - 1);
	cout << input[index - 1] + cut << endl;
}

cut을 구하는 것이 핵심인 코드입니다. ㅎㅎ

(이때 index가 배열의 크기를 넘어서지 않기위해 n + 1개 만큼의 배열로 선언해주어야 합니당.)

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

n / m 의 몫과 나머지를 출력하면 되는 문제.

처음에 별거 아니잖아? 하고 덤벼들었는데 1 ~ 10^1000 범위의 숫자에 대한 연산이 필요한 문제였습니다.

입력 값이 1001 "자리" 가 나온다는 의미입니다.  ("천억" 의 자리는 0000,0000,0000 12자리밖에 되지 않네요.)

풀이에 떠올린 아이디어는 이렇습니다.

우선 입력은 문자열로 받고 계산하기 편하게 숫자 배열로 만들어줍니다.

그리고 뺄셈을 통해 몫과 나머지를 구해줄 겁니다.

먼저 우리가 나누기를 진행할 때를 기억해보면

483216 / 30

        1 

    ㅡㅡㅡㅡㅡㅡ 

30) 4 8 3 2 1 6

     3 0

    ㅡㅡㅡㅡㅡㅡ

     1 8 3

        1 6

    ㅡㅡㅡㅡㅡㅡ 

30) 4 8 3 2 1 6

     3 0

    ㅡㅡㅡㅡㅡㅡ

     1 8 3

     1 8 0

    ㅡㅡㅡㅡㅡㅡ

          3 2

          .....

이런식으로 진행이 됩니다.

이 과정을 컴퓨터에게 시키면 몫과 나머지를 구할 수 있습니다.

대신 앞에서부터 뺄셈을 진행할 것이기 때문에 뺄셈이 진행되는 도중 불가능한 것이 판명되면

뺀 숫자들을 다시 더해주고 복구시켜 주겠습니다.

ex)

  574 / 575 진행 시

  574

- 5

ㅡㅡㅡ

    74

-   7

ㅡㅡㅡ

      4

-     5

 (진행이 불가능 하므로 앞의 57을 복구시켜 줘야됩니다.)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> moneyArray;
vector<int> personsArray;

int moneyLength;
int personsLength;

void MakeIntArray(vector<int>& arr, string& str, int length)
{
	for (int i = 0; i < length; ++i)
	{
		arr[i] = str[i] - '0';
	}
}

void PrintQuotient(vector<int>& quotient)
{
	int size = quotient.size();

	if (size == 0) //몫이 없는 경우
	{
		cout << 0;
		return;
	}

	for (int i = 0; i < size; ++i)
	{
		cout << quotient[i];
	}
}

void PrintRemainder()
{
	int i = 0;

	while (i < moneyLength && moneyArray[i] == 0)
	{
		i++;
	}

	if (i < moneyLength) //나머지가 있는 경우
	{
		while (i < moneyLength)
		{
			cout << moneyArray[i];
			i++;
		}
	}
	else //나머지가 없는 경우
	{
		cout << 0;
	}

	cout << endl;
}

int Subtraction(int base)
{
	int index = base - personsLength + 1;
	//47664
	//46669
	//현재 base = 4, personsLength = 5로
	//index = 0 이 됩니다. 비교할 첫 시작점을 의미합니다.

	for (int i = 0; i < personsLength; ++i)
	{
		if (moneyArray[index + i] - personsArray[i] < 0) //앞에서 자리를 빌려와야됨
		{
			int j = 1;

			//47664
			//46669
			//0100 <4 - 9>
			//위 부분에서 앞자리에 빌려올 곳을 찾아야됩니다.
			while (index + i - j >= index && moneyArray[index + i - j] == 0)
			{
				j++;
			}

			if (index + i - j < index) //빌려올 곳이 시작지점을 넘어서면 못빌려옵니다.
			{
				return i; //뺄셈이 불가능하기에 빼준 앞 부분들까지 다시 더해주기 위해
						  //인덱스를 반환합니다.
			}

			moneyArray[index + i - j]--; //요기서 빌릴 수 있네요.
			j--;
			while (j > 0)
			{
				moneyArray[index + i - j] = 9; //빌려오면서 거친 부분들은 9로 만들어줍니다.
				j--;
			}
			//0100 -> 0099 가 됩니다.

			moneyArray[index + i] += 10 - personsArray[i]; //0099(14 - 9) = 00995
		}
		else //뺄셈이 가능하면 그냥 빼주기
		{
			moneyArray[index + i] -= personsArray[i];
		}
	}

	return -1; //뺄셈이 성공하면 다시 더해줄 필요가 없음
}

void Sum(int base, int limit) //뺄셈이 실패하기 - 1 지점까지 다시 더해서 복구해주기
{
	int index = base - personsLength + 1;

	for (int i = limit - 1; i >= 0; --i)
	{
		moneyArray[index + i] += personsArray[i];
	}
}

int main()
{
	string money, persons;
	vector<int> quotient;

	cin >> money >> persons;

	moneyLength = money.length();
	personsLength = persons.length();

	moneyArray.resize(moneyLength);
	personsArray.resize(personsLength);

	MakeIntArray(moneyArray, money, moneyLength);
	MakeIntArray(personsArray, persons, personsLength);

	for (int i = personsLength - 1; i < moneyLength; ++i)
	{
		//만약 1234 / 124의 경우
		//123 / 124 는 실패합니다.
		//이제 234 / 124 비교 차례인데
		//앞의 숫자(1)가 남아있는걸 갖고와주는 작업입니다.
		if (i - personsLength >= 0)
		{
			moneyArray[i - personsLength + 1] += moneyArray[i - personsLength] * 10;
			moneyArray[i - personsLength] = 0;
		}

		int div = 0; //몫

		while (true)
		{
			int failPos = Subtraction(i); //빼질때까지 계속 빼보기

			if (failPos > -1) //더이상 나눌수(뺄 수) 없으면 복구해주고 종료.
			{
				Sum(i, failPos);
				break;
			}

			div++;
		}

		if (quotient.size() == 0 && div == 0) //첫 몫이 0인지 확인
		{
			continue;
		}
		else
		{
			quotient.push_back(div);
		}
	}

	PrintQuotient(quotient);
	cout << " ";
	PrintRemainder();
}

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

dp에 어떻게 저장해야 될까? 생각이 안나서

구글링으로.. 다른 사람의 코드를 참고했고 이제 좀 이해가 되었다. (나중에 까먹을까봐 적어둔다 ㅠ)

사건을 중심으로 전개를 해야되는 방법이다.

최대 1000 * 1000 의 상태로 문제를 바꿔서 바라보는 방법이 필요했다. (이게 어려움..)

[ 1번 경찰차 최근 해결 사건 번호 ] [ 2번 경찰차 최근 해결 사건 번호 ]

DFS를 통해 사건 담당 상태에 따라 값을 갱신시켜준다.

겹치는 부분은 dp 값을 이용하여 대체가 가능해진다.

아래는 사건이 4개인 경우 DFS를 진행한 결과이다.

크기가 크지 않아 겹치는 주황 부분이 많지 않지만 사건의 갯수가 많아지면

생략되는 탐색이 많아지기에 효과를 볼 수 있다.

FindMinPath 가 깊이 우선 탐색을 하며 dp를 갱신하는 핵심 함수이고,

ShowPath에선 p1, p2의 현재 위치에서 탐색 비용과 이미 dp에 저장된 결과값의 최소값을

따라가며 경로를 알 수 있게 된다.

ex) (p1 : 경찰차1 , p2 : 경찰차2)

[p1][p2] 에 대한 최적의 루트는 이미 FindMinPath를 통해 갱신되었기에

경찰차1 목적지의 비용 + dp[목적지][p2]

경찰차2 목적지의 비용 + dp[p1][목적지]

중 어디가 더 비용이 적은지 탐색하며 p1과 p2를 바꿔주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct Position
{
	int x, y;
}Position;

vector<Position> pos;
int dp[1002][1002];
int n, w;

int GetDistance(Position pos1, Position pos2)
{
	return abs(pos1.x - pos2.x) + abs(pos1.y - pos2.y);
}

int FindMinPath(int p1, int p2, int next)
{
	if (next > w) //사건의 수가 w개를 넘으면 종료합니다.
	{
		return 0;
	}

	if (dp[p1][p2] != 0)
	{
		return dp[p1][p2];
	}
        //GetDistance를 통해 해밍턴 거리를 구하고 DFS 탐색을 이어나갑니다.
	int p1Cost = GetDistance(pos[p1], pos[next]) + FindMinPath(next, p2, next + 1);
	int p2Cost = GetDistance(pos[p2], pos[next]) + FindMinPath(p1, next, next + 1);

	return dp[p1][p2] = min(p1Cost, p2Cost);
}

void ShowPath(int p1, int p2)
{
        //dp를 통해 경로를 역추적합니다.
	for (int next = 1; next <= w; ++next)
	{
		int p1Cost = GetDistance(pos[p1], pos[next]) + dp[next][p2];
		int p2Cost = GetDistance(pos[p2], pos[next]) + dp[p1][next];

		if (p1Cost < p2Cost)
		{
			cout << 1 << endl;
			p1 = next;
		}
		else
		{
			cout << 2 << endl;
			p2 = next;
		}
	}
}

int main()
{
	cin.tie(0);
	cin >> n >> w;

        //편의를 위해 미리 경찰차1, 경찰차2 위치를 저장해줍니다.
	pos.resize(w + 2);
	pos[0] = Position{ 1, 1 };     //0 을 경찰차1 위치로 정해줍니다.
	pos[w + 1] = Position{ n, n }; //w + 1 을 경찰차2 위치로 정해줍니다.

	for (int i = 1; i <= w; ++i) //1 ~ w 까지만 입력을 받습니다.
	{
		cin >> pos[i].x >> pos[i].y;
	}

        //첫번째 경찰차 인덱스[0], 두번째 경찰차[w + 1], 첫 사건 번호[1]
	int cost = FindMinPath(0, w + 1, 1);
	cout << cost << endl;
        //첫번째 경찰차는 0, 두번째 경찰차는 w + 1
	ShowPath(0, w + 1);
}

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

8 x 8 크기의 체스판이지만 A1, B5 등의 문자열로 취급이 된다.

숫자는 행, 알파벳은 열을 의미하기에 문자를 숫자로 바꾸는 법을 알아야한다.

아스키코드 값을 외울필요는 없다. (항상 까먹음..)

[문자 -> 숫자 변환]

'1' -> '1' - '0' = 1

'2' -> '2' - '0' = 2

(A가 1로 시작하기때문에 + 1을 해준다)

'A' -> 'A' - 'A' + 1 = 1

'B' -> 'B' - 'A' + 1 = 2

반대로는?

[숫자 -> 문자]

(행)

1 -> 1 + '0' = '1'

2 -> 2 + '0' = '2'

(열) (반대로 -1을 해줘야된다.)

1 -> 1 + 'A' - 1 = 'A'

2 -> 2 + 'A' - 1 = 'B'

이제 위의 방식대로 위치를 알 수 있게 되었다.

이제 행과 열이 1 <= 행, 열 <= 8 인 경우만 옮기게 해준다.

이동 가능한지 체크, 돌과 만나는지, 돌도 이동 가능한지 체크만 해주면 끝!

#include <iostream>
#include <string>

using namespace std;

const int SIZE = 8;

void GetPosition(string& pos, int& row, int& col)
{
	row = pos[1] - '0';
	col = pos[0] - 'A' + 1;
}

void GetDirection(char& command, int& dirRow, int& dirCol)
{
	switch (command)
	{
	case 'R':
		dirCol++;
		break;
	case 'L':
		dirCol--;
		break;
	case 'B':
		dirRow--;
		break;
	case 'T':
		dirRow++;
		break;
	default:
		break;
	}
}

bool IsValidPosition(int row, int col)
{
	return 0 < row && row <= SIZE &&
		0 < col && col <= SIZE;
}

void SetPosition(string& pos, int row, int col)
{
	pos[0] = 'A' + (col - 1);
	pos[1] = row + '0';
}

int main()
{
	string kingPosition, stonePosition, move;
	int moveCount, kingRow, kingCol, stoneRow, stoneCol;

	cin >> kingPosition >> stonePosition >> moveCount;

	GetPosition(kingPosition, kingRow, kingCol);
	GetPosition(stonePosition, stoneRow, stoneCol);
	
	for (int i = 0; i < moveCount; ++i)
	{
		int dirRow = 0, dirCol = 0;

		cin >> move;

		for (int j = 0; j < move.length(); ++j)
		{
			GetDirection(move[j], dirRow, dirCol);
		}

		if (IsValidPosition(kingRow + dirRow, kingCol + dirCol))
		{
			string preKingPosition = kingPosition;
			int preKingRow = kingRow;
			int preKingCol = kingCol;

			kingRow += dirRow;
			kingCol += dirCol;

			SetPosition(kingPosition, kingRow, kingCol);

			if (kingPosition == stonePosition)
			{
				if (IsValidPosition(stoneRow + dirRow, stoneCol + dirCol))
				{
					stoneRow += dirRow;
					stoneCol += dirCol;

					SetPosition(stonePosition, stoneRow, stoneCol);
				}
				else
				{
					kingPosition = preKingPosition;
					kingRow = preKingRow;
					kingCol = preKingCol;
				}
			}
		}
	}

	cout << kingPosition << " " << stonePosition << endl;
}

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

위와 같이 Z 모양으로 순회하며 확장이 된다. 사실 N값은 없어도 되고,

Row, Column 값으로 정답을 구할 수 있다.

위의 패턴을 분석해보면 아래와 같은 모양이 됨을 알 수가 있었다.

(실수로 숫자가 0이 아닌 1로 시작하였다..)

위의 문제에서 Row와 Column은 0으로 시작된다.

[0, 0] = 1

[0, 1] = 2

[1, 0] = 3

[1, 1] = 4

이런식의 값을 갖게 된다.

자 여기서 r = 2, c = 2를 찾아보면?

정답은 13이 된다. (실제 답은 12가 나와야 됩니다 실수로 1부터 시작했네유 :D )

이번엔 계산으로 구해보면 "r과 c는 2의 몇 제곱수에 걸쳐있느냐?" 를 찾으면 된다.

이것으로 r과 c의 경계를 알 수 있고 미리 계산이 가능해진다.

(대신 인덱스가 0부터 시작하기 때문에 r == 2^x 인 경우도 경계를 넘는것으로 인정해주어야 한다.)

아래의 그림을 확인해보자. 뭔가 떠오르지 않을까!

위의 초록 경계 구역을 걸러낼 수 있게된다. 저 부분은 미리 더해주고 복잡하니깐 없는 것으로 취급해도 된다.

(인덱스가 0부터 시작하기 때문에 r == 2^x 인 경우도 경계를 넘는것으로 인정해주어야 한다.)

row = 2로 4 x 4의 구역에 들어간다. 이전 구역 2 x 2 부분은 2번 넘어왔다는 것을 알 수 있다.

col = 2로 4 x 4의 구역에 들어간다. 이전 구역 2 x 2 부분을 1번 넘어왔다.

즉 위의

         row와 col 은 4 x 4 로 4의 경계에 있기 때문에

                          4 / 2 = 2 가 이전 경계가 된다.

          (row 2개 구역) + (col 1개 구역)

             ( 2 x 2 x 2 ) + ( 2 x 2 )

           를 계산해주고 치워버려도 된다.

어차피 패턴은 똑같기 때문이다. 남는 것은 아래와 같다.

 남기기 위해 row와 col 값을 변경해준다. 계산이 끝난 부분은 필요 없기 때문이다.

  row : 미리 계산 된 곳은 빼준다.   row = row(2) - 2^2 / 2 = 0

  col  : 미리 계산 된 곳은 빼준다.   col = col(2) - 2^2 / 2 = 0

row = 0, col = 0 으로 이제 위의 입장에 봤을 때 0, 0이 정답이다. (원래는 12가 정답)

만약에 남은 인덱스가 0, 0 이 아니라 2, 4 등의 다른 숫자가 나오면 해당 부분도 계속 2의 제곱 수로

경계를 걸러주며 갯수는 결과에 더해주고, 해당 구역은 제거해 주면서 반복하면 된다.

중요한 것은

(row, col 인덱스가 0부터 시작하기 때문에 r == 2^x 인 경우도 경계를 넘는것으로 인정해준다.)

row가 경계를 넘게 되면 2개의 구역을 넘게 된다. 2개의 구역에 대해 더해주기.

col은 왼편의 1개의 구역만을 넘기때문에 1개의 구역에 대해서만 더해주면 된다.

#include <iostream>

using namespace std;

int main()
{
	int n, r, c;
	int result = 0;

	cin >> n >> r >> c;

	while (r > 0)
	{
		int size = 2;
		while (size <= r)
		{
			size *= 2;
		}

		size /= 2;
		result += size * size * 2;
		r -= size;
	}

	while (c > 0)
	{
		int size = 2;
		while (size <= c)
		{
			size *= 2;
		}

		size /= 2;
		result += size * size;
		c -= size;
	}

	cout << result << endl;
}

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

위키백과:

그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.

이 외에도 홀수개의 사이클이 없어야 한다는데 이게 이해가 잘 안됐었는데 그림으로 다시 확인해보면

홀수 사이클에선 파랑 - 파랑 으로 같은 색끼리 연결이 될 수 밖에 없기 때문에 이분 그래프가 아니다.

DFS나 BFS를 통해 색을 칠하며 정점을 탐색하는 것이 중요한 문제였다.

코드에서는 DFS에서 탐색을 하면서, 이분 그래프 여부도 같이 체크해줬다.

color는 방문전에는 0으로 시작하고, 탐색 시 color % 2 + 1 을 통해 색을 반전시켜줬다.

color = 1인 경우 1 % 2 + 1 = 2

color = 2인 경우 2 % 2 + 1 = 1

memset도 필요한 부분까지만 리셋해주며 코드를 좀 더렵혀봤다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int color[20001];
bool isBipartiteGraph;

void DFS(vector<vector<int>>& list, int current, int nextColor)
{
	int size = list[current].size();

	for (int i = 0; i < size; ++i)
	{
		if (!isBipartiteGraph)
		{
			return;
		}

		int next = list[current][i];

		if (color[next] == 0)
		{
			color[next] = nextColor;
			DFS(list, next, nextColor % 2 + 1);
		}
		else if (color[current] == color[next])
		{
			isBipartiteGraph = false;
			return;
		}
	}
}

int main()
{
	int testCase;
	int v, e;
	int from, to;

	cin.tie(0);
	cin >> testCase;

	while (testCase--)
	{
		vector<vector<int>> list;
		isBipartiteGraph = true;

		cin >> v >> e;

		list.resize(v + 1);
		memset(color, 0, sizeof(int) * (v + 1));

		for (int i = 0; i < e; ++i)
		{
			cin >> from >> to;

			list[from].push_back(to);
			list[to].push_back(from);
		}

		for (int i = 1; i <= v; ++i)
		{
			if (color[i] == 0)
			{
				color[i] = 1;
			}

			DFS(list, i, color[i] % 2 + 1);
		}

		if (isBipartiteGraph)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
}