저그유저의 프로그래밍

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;
		}
	}
}

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

배열 인덱스에 해당하는 곳을 지그재그로 출력하는 문제이다.

1/1 1/2 1/3 1/4 ...

2/1 2/2 2/3 2/4 ...

3/1 3/2 3/3 3/4 ...

...    ...    ...   ...   ...

[1]      [2]       [3]      [4]      [5]      [6]      [7]

1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> 1/3 -> 1/4 -> ...

식으로 진행이 된다.

규칙을 먼저 찾아보면

1. 최대 숫자가 1, 2, 3, 4 순서대로 증가한다.

ex)
 1 시작 => 1/1

 2 시작 => 1/2, 2/1

 3 시작 => 3/1, 2/2, 1/3

2. Ascending (오름차순 ex: 1 2 3 4) , Descending (내림차순 ex: 4 3 2 1)이 반복되는 형태로 되어있다.

2번 규칙 순서가 바뀌는 것을 제외하고 1번 규칙만을 놓고 나열을 해보면 아래와 같이 숫자가 나열 된다.

1/1

1/2 2/1

1/3 2/2 3/1

1/4 2/3 3/2 4/1

잘 보면

X / 최대 숫자

X + 1 / 최대 숫자 - 1

...

이런식으로 흘러가는 걸 알 수 있다.

이걸 이용해서

X - 최대 숫자 > 0 이면

   X = X - 최대숫자, 최대숫자 증가

X - 최대 숫자 <= 0 이면

   오름차순 or 내림차순 순서에 따라 X / 최대 숫자 - X + 1 또는 최대 숫자 - X + 1 / X

  를 출력해주기만 하면 된다. (이렇게 작성함)

#include <iostream>

using namespace std;

int main()
{
	int x;
	int num = 1;
	bool isAscending = true;

	cin >> x;

	while (true)
	{
		isAscending = !isAscending;

		if (x - num <= 0)
		{
			if (isAscending)
			{
				cout << x << "/" << num - x + 1 << endl;
			}
			else
			{
				cout << num - x + 1 << "/" << x << endl;
			}

			break;
		}

		x -= num;
		num++;
	}
}

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

SCC (Strongly Connected Component) 는 그래프 내에서 사이클을 이루는 각각의 그룹을 의미한다.

연결이 되어 있지 않아 1개인 경우도 하나의 그룹으로 취급한다.

문제가 어려워 접근 방법을 몰랐는데

아래 블로그에 SCC에 대해서 [코사라주 알고리즘]과 [타잔 알고리즘]에 대해서 잘 소개해주고 있다.

친절한 설명 덕분에 잘 이해할 수 있게 되었고 직접 실습하고 기억을 남긴다.

https://jason9319.tistory.com/98

개념을 간단히 정리해보면 이렇다.

[코사라주 알고리즘]

1. 입력에 대한 원본 그래프가 필요하다 (리스트 또는 배열)

2. 역방향 그래프가 필요하다. (입력에 대해서 역방향 ex)  원본이 1 -> 2 라면 2 -> 1로 저장

3. 방문여부 체크용 배열이 필요하다.

4. 스택이 필요하다. <- 이 부분은 벡터로 활용해도 된다. (dfs 함수 재사용을 위해 벡터로 사용해주었다.)

step

 1. 원본을 입력 받는다. 동시에 역방향 그래프도 만들어준다.

 2. 원본 그래프에 대한 dfs 를 통해 후위 순회 순서대로 스택에 정점 번호를 저장해준다. (트리의 후위 순회 개념)

 3. 스택에서 정점 번호를 하나씩 꺼내고 방문했는지 확인한다.

   (이미 탐색 o) pass

   (이미 탐색 x) 역방향 그래프로 다시 dfs 를 해본다. 그리고 해당 결과에 이용된 정점들을 저장해준다.

                    이 정점들이 하나의 사이클, 즉 그룹을 이루고 있는 것들이다.

 4. 문제에서 순서대로 출력하는 것을 원하기 때문에 sort를 해준다.

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

using namespace std;

const int SIZE = 10001;

bool visited[SIZE];

void dfs(vector<vector<int>> &linkList, vector<int> &subVector, int vertex)
{
	int size = linkList[vertex].size();

	visited[vertex] = true;
	
	for (int i = 0; i < size; ++i)
	{
		int next = linkList[vertex][i];

		if (visited[next])
		{
			continue;
		}

		dfs(linkList, subVector, next);
	}
	
	subVector.push_back(vertex);
}

int main()
{
	vector<vector<int>> link;
	vector<vector<int>> reverseLink;
	vector<vector<int>> group;
	vector<int> arrayStack;
	vector<int> subGroup;

	int v, e;
	int from, to;

	cin.tie(0);
	cin >> v >> e;

	link.resize(v + 1);
	reverseLink.resize(v + 1);

	for (int i = 0; i < e; ++i)
	{
		cin >> from >> to;
	
		link[from].push_back(to);
		reverseLink[to].push_back(from);
	}

	for (int i = 1; i <= v; ++i)
	{
		if (!visited[i])
		{
			dfs(link, arrayStack, i);
		}
	}

	memset(visited, false, sizeof(visited));

	for (int i = arrayStack.size() - 1; i >= 0; --i)
	{
		int vertex = arrayStack[i];

		if (visited[vertex])
		{
			continue;
		}

		dfs(reverseLink, subGroup, vertex);
		
		sort(subGroup.begin(), subGroup.end());
		group.push_back(subGroup);
		
		subGroup.clear();
	}

	sort(group.begin(), group.end());
    
	cout << group.size() << endl;
	for (int i = 0; i < group.size(); ++i)
	{
		for (int j = 0; j < group[i].size(); ++j)
		{
			cout << group[i][j] << " ";
		}
		cout << "-1" << endl;
	}
}

[타잔 알고리즘]

타잔 알고리즘은 역방향 그래프가 필요없다. 대신에 그룹화가 되어있는지를 체크해줘야 한다.

1. 원본 그래프

2. 방문여부 배열

3. 그룹화여부 배열

4. 스택

step

 1. 원본을 입력 받는다.

 2. 방문하지 않은 정점부터 SCC 탐색을 시작해준다.

    현재 탐색 순서(ret)와 방문여부(visited)를 지정해준다.

    (이 부분을 통해 나중에 몇 번째부터 그룹화를 해줄지 정해주게 된다.)

    그리고 스택에 현재 방문한 정점을 저장한다.

 3. 현재 정점과 연결 된 정점을 찾아본다.

   3-1. 방문했었고 이미 SCC그룹이 확인된 곳)

          그냥 지나친다.

   3-2. 아직 방문하지 않은 곳)  ret = min ( ret, SCC(next) );

          해당 정점을 기준으로 SCC 탐색을 반복한다. 이 때 현재 탐색 순서의 갱신이 필요할 수 있다.

         다음 방문하는 곳에서 그룹의 기준이 될 곳을 만날 수 있기 때문에 현재 탐색 순서 (ret)을 더 작은 값으로

         갱신해줘야 한다.

   3-3. 방문했었고, 아직 SCC그룹화 되어있지 않은 곳)  ret = min( ret, visited[next] );

          현재 탐색 순서 (ret)와 해당 탐색 순서 (visited[next])를 비교하여 작은 곳을 기준으로 삼아준다. (ret을 더 작게) 

          이 부분이 어려웠다. 의미하는 것은 아래 그림으로..!

============================================================================

 1번 정점에서 탐색을 시작한다. ret = 1, visited[1] = 1이고 스택에 1을 넣어준다.

 이웃 노드로 미방문 노드 2번이 있다. 이제 SCC(2) 로 간다.

 ret = 2, visited[2] = 2로 시작하고 스택에 2를 넣어준다.

 "-" 는 이미 그룹화가 되어있기 때문에(방문도 되었기에) 더 이상 진행할 필요가 없다. 그냥 넘어가면 된다.

 2->1 은 연결이 되어있다. 1번은 이미 지나왔기 때문에 방문 상태이고 그룹화는 되어있지 않다.

1번과 2번은 그룹으로 묶일 수 있게 되는데, 가장 최초의 탐색 순서로 ret을 지정해준다. 이유는 이 ret을 통해

현재 탐색 지점 ~ 최초 탐색 지점 까지 스택에서 꺼내서 그룹으로 묶어주기 위해서이다! ( 스택 { 1 , 2(top) } )

 결과적으로 2번의 Ret = 1, Visited[2] = 2가 된다.

============================================================================

 4. 현재 Visited와 Ret이 동일한지를 확인한다. 동일하지 않다면 그냥 넘어가면 되고 (ret != visited[index])

   동일하다면 스택에서 현재 번호가 나올때까지 모두 꺼낸다. 이 정점들이 그룹화를 이루고 있는 곳이다.

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

using namespace std;

int order = 1;
bool isScc[10001];
int visited[10001];
vector<vector<int>> list;
vector<vector<int>> group;
stack<int> s;

int SCC(int index)
{ 
	int ret = visited[index] = order++;
	s.push(index);

	int size = list[index].size();
	for (int i = 0; i < size; ++i)
	{
		int next = list[index][i];

		if (visited[next] == 0)
		{
			ret = min(ret, SCC(next));
		}
		else if (!isScc[next])
		{
			ret = min(ret, visited[next]);
		}
	}

	if (ret == visited[index])
	{
		vector<int> subGroup;
		while (true)
		{
			int vertex = s.top();
			s.pop();

			subGroup.push_back(vertex);
			isScc[vertex] = true;

			if (vertex == index)
			{
				break;
			}
		}

		sort(subGroup.begin(), subGroup.end());
		group.push_back(subGroup);
	}

	return ret;
}

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

	cin.tie(0);
	cin >> v >> e;

	list.resize(v + 1);
	for (int i = 0; i < e; ++i)
	{
		cin >> from >> to;
		list[from].push_back(to);
	}

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

		SCC(i);
	}

	sort(group.begin(), group.end());

	cout << group.size() << endl;
	for (int i = 0; i < group.size(); ++i)
	{
		for (int j = 0; j < group[i].size(); ++j)
		{
			cout << group[i][j] << " ";
		}
		cout << "-1" << endl;
	}
}

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

#include <iostream>

using namespace std;

int GetMin(int a, int b)
{
	return a < b ? a : b;
}

int BinarySearch(int n, int k)
{
	int left = 1, right = k;

	while (left < right)
	{
		int mid = (left + right) / 2;
		int count = 0;

		for (int i = 1; i <= n; ++i)
		{
			count += GetMin(mid / i, n);
		}

		if (count < k)
		{
			left = mid + 1;
		}
		else
		{
			right = mid;
		}
	}

	return right;
}

int main()
{
	int n, k;
	cin >> n >> k;

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

다른 분들이 짠 코드를 봤는데 결국 똑같은 코드가 되어버렸다.

처음에 문제를 봤을 때 이걸 어떻게 이진탐색으로 푸는거지?? 생각이 들었지만 지금은 이해가 되었다.

문제는 이렇다.

2차원 n x n 크기의 배열 A가 있다. (모든 인덱스는 1부터 시작)

각 인덱스에 따라 [i][j] = i x j 의 값이 들어있다.

예를 들어

n = 3이면

[1][1] 1x1 = 1  [1][2] 1x2 = 2  [1][3] 1x3 = 3

[2][1] 2x1 = 2  [2][2] 2x2 = 4  [2][3] 2x3 = 6

[3][1] 3x1 = 3  [3][2] 3x2 = 6  [3][3] 3x3 = 9

이 배열을 B라는 1차원 오름차순 배열로 만든다.

B[1] = 1

B[2] = 2

B[3] = 2

B[4] = 3

B[5] = 3

B[6] = 4

B[7] = 6

B[8] = 6

B[9] = 9

이 중에서 k번째의 값은 무엇인가?

   k가 7이라면 B[7] = 6

위의 코드에서 핵심은 count를 세는 방법에 있다.

다시 한번 배열을 살펴보면

[1][1] 1x1 = 1  [1][2] 1x2 = 2  [1][3] 1x3 = 3        i = 1의 배수

[2][1] 2x1 = 2  [2][2] 2x2 = 4  [2][3] 2x3 = 6        i = 2의 배수

[3][1] 3x1 = 3  [3][2] 3x2 = 6  [3][3] 3x3 = 9        i = 3의 배수

즉 각 배수로 나누어봐서 그 결과가 내가 찾는 인덱스 값과 같다면 해당 숫자가 정답이 된다.

만약에 내가 B[4] (3)를 찾고 싶다면 위의 코드는 이렇게 동작이 된다.

left = 1, right = 4

mid = (1 + 4) / 2 = 2

for

i = 1   count += 2 / 1 (2)

i = 2   count += 2 / 2 (1)

i = 3   count += 2 / 3 (0)

count = 3으로 "2" 는 3번째 숫자란 의미가 된다.

4번째 숫자를 찾고 싶기 때문에

left = mid + 1을 해주고 다시 탐색을 해본다.

left = 3, right = 4

mid = (3 + 4) / 2 = 3

for

i = 1  count += 3 / 1 (3)

i = 2  count += 3 / 2 (1)

i = 3  count += 3 / 3 (1)

count = 5가 된다. 그러나 걱정할거 없다. 이미

B[3] = 2

B[4] = 3

B[5] = 3

으로 사잇값은 3으로 동일하기 때문이다.

추가적으로 GetMin(mid / i, n) 을 통해 더 작은 값으로 판별해주는데 예를 들어

6 x 6 배열에서

36번째를 찾게 된다면

left = 1, right = 36

mid = (1 + 36) / 2 = 18

i는 1일 때 18 / 1 = 18이 되어버린다.

n = 6 이므로 1x6 까지밖에 없는데 말이다.

수의 개수가 n을 넘어가버리면 모두 가능한 수로 취급하면 된다. mid / i, n 둘 중 작은 수를 더해주면 된다.

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

#include <stdio.h>
#include <string.h>

char n[10];
int result = -1;

void Swap(int a, int b)
{
    char temp = n[a];
    n[a] = n[b];
    n[b] = temp;
}

char GetMaxNum(int start, int length)
{
    char num = n[start];
    for (int i = start + 1; i < length; ++i)
    {
        if (num < n[i])
        {
            num = n[i];
        }
    }
    return num;
}

bool IsRightOrder(int length)
{
    for (int i = 1; i < length; ++i)
    {
        if (n[i - 1] < n[i])
        {
            return false;
        }
    }

    return true;
}

bool ExistSameNum(int length)
{
    for (int i = 1; i < length; ++i)
    {
        if (n[i - 1] == n[i])
        {
            return true;
        }
    }
    return false;
}

int GetMax(int a, int b)
{
    return a > b ? a : b;
}

int ArrayToNum(int length)
{
    int num = 0;
    for (int i = 0; i < length; ++i)
    {
        num = num * 10 + n[i] - '0';
    }
    return num;
}

void ChangeNumbers(int step, int k, int start, int length)
{
    if (step == k)
    {
        result = GetMax(result, ArrayToNum(length));
        return;
    }

    if (IsRightOrder(length))
    {
        if (!ExistSameNum(length) && (k - step) % 2 == 1)
        {
            Swap(length - 1, length - 2);
            result = GetMax(result, ArrayToNum(length));
            Swap(length - 1, length - 2);
        }
        else
        {
            result = GetMax(result, ArrayToNum(length));
        }

        return;
    }

    if (start + 2 == length)
    {
        Swap(start, start + 1);
        ChangeNumbers(step + 1, k, start, length);
        Swap(start, start + 1);
    }
    else
    {
        char maxNum = GetMaxNum(start, length);

        if (n[start] == maxNum)
        {
            ChangeNumbers(step, k, start + 1, length);
        }

        for (int i = start + 1; i < length; ++i)
        {
            if (n[i] == maxNum)
            {
                Swap(start, i);
                ChangeNumbers(step + 1, k, start + 1, length);
                Swap(start, i);
            }
        }
    }
}

int main()
{
    int k;
    int length;

    scanf("%s %d", n, &k);
    length = strlen(n);

    if (length <= 1 || (length == 2 && n[1] == '0'))
    {
        printf("-1\n");
        return 0;
    }

    ChangeNumbers(0, k, 0, length);
    printf("%d\n", result);
}

처음에 굉장히 쉬운줄 알았는데 예상치 못한 테스트 케이스가 많았던 문제였다.

처음부터 알아낸 조건과 삽질하며 알아낸 조건들이 있다. 정리를 해보면

1. 1개면 교환이 불가능하다. (-1 출력)

2. 2개일 때 뒤에 0이 있다면 교환이 불가능하다. (-1 출력)

    (여기까지 미리 1~9, 10, 20, 30 ... 90 까지의 숫자는 걸러준다.)

3. 당연하게도 무조건 가장 큰 수가 맨 앞으로 가면 좋다! 그러나 고려해야 될 조건이 두 가지 있다.

  3-1. 가장 큰 수가 "맨 앞에만" 있다.

        ex) 930 => 9를 스킵하고 30에 대해서만 교환을 해주면 된다.

             97  => 2개이기 때문에 스킵이 불가능하다. 무조건 교환해줘야 된다.

  3-2. 가장 큰 수가 "여러개" 일 경우이다.

        (처음에 가장 뒤에놈을 앞으로 옮겨줬는데 아래 테스트 케이스 중 그러면 안되는 것이 있다.)

        ex) 9989 1 => 9998

             3699 2 => 9963

             6399 2 => 9963 (이놈)

 4. 이미 차례대로 정렬되어 있다면 마지막 2개만 교환해주거나 교환해줄 필요가 없어진다.

        ex) 9876 1 => 9867,    9876 2 => 9876

             9987 x => (맨 앞의 99만 계속 교환해주면 끝) 9987

3번 조건의 가장 큰 수가 여러개 있는 경우에 탐색의 분기점이 생긴다.

그래서 Swap 이 후 다시 Swap을 통해 기존의 배열을 유지시키며 탐색을 하게 만들었다.

코드를 보면 나처럼 멍청한 사람이 코딩하면 이렇게 코드가 길어지고 시행착오를 겪게 되며 시간을

많이 쓰게 된다는 것을 다시 느끼게 된다.. ㅠㅠ

다른 사람이 잘 작성한 코드도 보면서 더 쉽고 간결하게 짤 수 있는 방법도 보고 이해해야 된다!

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

#include <stdio.h>

long long BinarySearch(long long start, long long end, long long x, long long y, long long z)
{
	long long mid, z2;
	long long result = -1LL;

	while (start < end)
	{
		mid = (start + end) / 2LL;
		z2 = (y + mid) * 100LL / (x + mid);

		if (z2 <= z)
		{
			start = mid + 1LL;
		}
		else if (z < z2)
		{
			end = mid;
			result = end;
		}
	}

	return result;
}

int main()
{
	long long x, y, z, result;

	scanf("%lld %lld", &x, &y);
	z = y * 100LL / x;

	result = BinarySearch(0, x + 1, x, y, z);
	printf("%lld\n", result);
}

이진 탐색을 활용하여 결과를 구할 수 있었다.

퍼센트로 나타내기 위해선 소수점 2자리만 필요하기 때문에 100판 중 40판을 이겼다면

40 * 100 / 100 으로 정수형이기 때문에 소수점을 제외하고 나타낼 수 있다. ( 4000 / 100 = 40 )

이 때 int형은 오버플로우가 발생할 수 있기에 모두 long long 형으로 설정해주었다.

계산 중 실수했던 부분이 게임을 이길수록 전체 판수도 함께 증가해야 된다는 것이었다.

새로운 승률 z2 = (기존 승리 + 추가 승리) * 100 / (전체 판수 + 추가 승리)

BinarySearch 매개변수인 long long end 값은 전체 판수 + 1 (x + 1)로 해주었다.

이 값이 현재 로직에서 탐색의 최대 범위이다.

전체 판수 : 1000000000 (10억)
이긴 판수 :  980000000 (9억 8천)

위의 경우는 총 10억판을 이기면 승률이 98%에서 99%로 올라가게 된다. (1980000000 / 2000000000)

근데 이진 탐색 로직을 보면 z < z2 (기존 승률 < 새로운 승률) 인 경우에만 result를 갱신하게 된다.

end 값이 줄어들어야 result가 갱신이 되는데 end값이 곧 정답이기에 작아질 수가 없기 때문이다.

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

#include <stdio.h>
#include <stdlib.h> //system("pause") 쓰기 위한 라이브러리

char map[10000][501]; //char 배열은 마지막 null 문자 들어가야되서 크기 + 1
int used[10000][500];
int dirR[3] = { -1, 0, 1 };

int maxRow, maxCol;
int result;
bool finished;

//현재 진행 상태를 볼 수 있게 만든 함수
void PrintState()
{
	printf("\n");
	for (int i = 0; i < maxRow; ++i)
	{
		for (int j = 0; j < maxCol; ++j)
		{
			if (map[i][j] == 'x')
			{
				printf("x");
				continue;
			}
			printf("%d", used[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	system("pause"); // 키를 누를 때까지 멈춤
}

void DFS(int row, int col, int num) //Depth First Search
{
	//PrintState(); //dfs 탐색 순서를 보고 싶다면 주석 제거

	if (col == maxCol - 1)
	{
		result++;
		finished = true;
		return;
	}

	int nextCol = col + 1;
    
	for (int i = 0; !finished && i < 3; ++i)
	{
		int nextRow = row + dirR[i];

		if (0 <= nextRow && nextRow < maxRow &&
			map[nextRow][nextCol] == '.' &&
			used[nextRow][nextCol] == 0)
		{
			used[nextRow][nextCol] = num;
			DFS(nextRow, nextCol, num);
		}
	}
}

int main()
{
	scanf("%d %d", &maxRow, &maxCol);

	for (int i = 0; i < maxRow; ++i)
	{
		scanf("%s", map[i]);
	}

	for (int i = 0; i < maxRow; ++i)
	{
		finished = false;
		used[i][0] = i + 1;

		DFS(i, 0, i + 1);
	}

	PrintState(); //탐색 완료 된 형태 출력
	printf("%d\n", result);
}

깊이 우선 탐색이 필요한 문제였다.

그리고 탐색이 성공하면 기존의 탐색도 반드시 종료시켜야 된다.

이걸 안해주면 다음과 같은 상황이 발생하게 된다..

지 혼자 모든 곳을 다 점령해버린다.

ex) 4x4

   1111

   xx11

   xxx1

   xxxx

이를 위해 전역변수로 bool finished를 선언해주었고,

탐색 전에 finished = false,

탐색이 성공하면 finished를 true로 변경해준다.

DFS for문의 조건이 finished == false && i < 3 으로 되어있기에

한 번이라도 마지막 지역에 도착했다면 다른 탐색을 하지 않을 수 있게 된다.

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

#include <cstdio>
#include <vector>

using namespace std;

typedef struct Horse
{
	int row, col, dir;
	bool isBottom;
}Horse;

const int SIZE = 12;

vector<int> over[11];
Horse horse[11];

int map[SIZE][SIZE];
int unit[SIZE][SIZE];

int dirR[4] = { 0, 0, -1, 1 };
int dirC[4] = { 1, -1, 0, 0 };
int n;

int ReverseOrder(int index)
{
	vector<int> v = over[index];
	int size = v.size();

	if (size <= 1) //위에 쌓인게 없으면 그대로 둔다.
	{
		return index;
	}

	horse[index].isBottom = false;
	int row = horse[index].row;
	int col = horse[index].col;

	for (int i = 0; i < size / 2; ++i)
	{
		int temp = v[i];
		v[i] = v[size - 1 - i];
		v[size - 1 - i] = temp;
	}

	int newIndex = v[0]; //새로운 맨 밑이 탄생하였다.

	over[newIndex] = v;  //새로운 밑으로 말들 배치를 저장해주고,
	over[index].clear(); //기존 것은 제거해준다.

	horse[newIndex].isBottom = true; //새로운 말이 맨 밑이 되었고
	unit[row][col] = v[newIndex];    //현재 unit도 새로운 말 인덱스가 저장된다.

	return newIndex;   //기준 인덱스가 바뀌어야 된다.
}

void TurnAroundDirection(int index)
{
	int dir = horse[index].dir;
	dir = dir / 2 * 2 + (dir + 1) % 2;
	horse[index].dir = dir;
}

bool IsOutOfBound(int row, int col)
{
	return row < 0 || n <= row || col < 0 || n <= col;
}

bool Move(int index, int preRow, int preCol, int newRow, int newCol)
{
	int size = over[index].size();
	int bottom = unit[newRow][newCol];

	unit[preRow][preCol] = 0; //이동 전 기존 좌표는 비워준다.

	for (int i = 0; i < size; ++i) //위에 있는 말들도 함께 이동시킨다.
	{
		int idx = over[index][i];
		horse[idx].row = newRow;
		horse[idx].col = newCol;
	}

	if (bottom != 0) //이동하는 곳에 말이 있다면?
	{
		horse[index].isBottom = false;

		//bottom 벡터 리스트 맨 뒤에 이동 된 index 벡터 리스트를 추가하는 작업이다.
		over[bottom].insert(over[bottom].end(), over[index].begin(), over[index].end());
		over[index].clear();

		if (over[bottom].size() >= 4) //이동 후 말이 4마리 이상이면 게임 오버
		{
			return true;
		}
	}
	else //말이 없으면 그냥 점령한다.
	{
		unit[newRow][newCol] = index;
	}

	return false;
}

bool ProcessFromColor(int index, int step)
{
	Horse h = horse[index];
	
	int d = h.dir;
	int newRow = h.row + dirR[d];
	int newCol = h.col + dirC[d];

	if (IsOutOfBound(newRow, newCol))
	{
		if (step == 0)
		{
			TurnAroundDirection(index);
			return ProcessFromColor(index, step + 1);
		}
		else
		{
			return false;
		}
	}

	switch (map[newRow][newCol])
	{
		case 1:

			index = ReverseOrder(index);
			return Move(index, h.row, h.col, newRow, newCol);

		case 2:

			if (step == 0)
			{
				TurnAroundDirection(index);
				return ProcessFromColor(index, step + 1);
			}
			
			return false;
		default:

			return Move(index, h.row, h.col, newRow, newCol);
	}

	return false;
}

int main()
{
	int row, col, dir;
	int k;
	int moved = 0;
	
	scanf("%d %d", &n, &k);

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			scanf("%d", &map[i][j]);
		}
	}

	for (int i = 1; i <= k; ++i) //말 번호는 1~k까지 쓸거지만
	{
		//row, col은 0, 0부터, dir는 0,1,2,3 으로 쓸거라 감소 시켜준다.
		scanf("%d %d %d", &row, &col, &dir);
		row--;
		col--;
		dir--;

		Horse h;
		h.row = row;
		h.col = col;
		h.dir = dir;
		h.isBottom = true;

		horse[i] = h; //말 정보를 등록하고
		unit[row][col] = i; //맵에도 말을 등록해준다.
		over[i].push_back(i); //리스트에는 자신을 먼저 등록해준다.
	}

	while (moved < 1000)
	{
		moved++;

		for (int i = 1; i <= k; ++i)
		{
			if (horse[i].isBottom == false)
			{
				continue;
			}

			bool isFinish = ProcessFromColor(i, 0);
			if (isFinish)
			{
				printf("%d\n", moved);
				return 0;
			}
		}
	}

	printf("-1\n");
	return 0;
}

오랜만에 문제를 하나 풀어봤는데, 머리속으론 로직이 정리되었는데 막상 짜니깐 오류가 생기고..

문제를 잘 못 이해한 부분때문에 이상한 답이 나오며 고생한 문제였다.

문제를 정리하면

n x n 맵에 하얀색(0), 빨간색(1), 파란색(2) 의 칸들이 존재하고

k개의 말들이 놓여있으며 말들은 방향을 갖고 있고, 해당 방향으로만 움직일 수 있다.

말들은 작은 숫자 순서대로 움직이고, 다른 말을 만나면 이동한 말(들)은 그 위에 쌓이게 되며

"가장 밑에 있는 말만 움직일 수 있게 된다."

하얀색 칸은 그냥 이동, (이동 시 해당 칸에 이미 말이 존재하면 해당 말 위에 올린다.)

빨간색 칸은 이동하기 전에 1,2,3 순서라면 3,2,1 순서로 변경하여 이동,

파란색 칸은 방향을 뒤로 바꾼 후 갈 수 있다면 이동, 불가능하다면 이동하지 않는다.

위의 빨간색 조건 때문에 이상한 답이 나왔었는데, 1턴에 모든 말들이 이동할 수 있는지 계속 체크해줘야 한다.

만약 (맨 밑)1, 2로 이루어진 말이 있는데 이 말이 빨간 칸에 가게 되면

2, 1로 바뀌게 된다. 그리고 2번 말이 이동할 수 있게 되며 이것이 1턴에 이루어지는 일들이다. 아래는 예제..

그렇게 이 조건을 몰라서 왜 안돼지?? 뻘짓을 하고 말았다고 한다..

코드를 설명해보면

우선 맵의 상태를 저장할 map[size][size] 배열과

말들의 위치를 저장할 unit[size][size] 로 따로 관리해주고 있다.

unit은 말의 번호를 저장해두고,

말들에 대해선 horse 배열을 통해 현재 위치 (row, col), 방향, 맨 밑에 있는지를 알아 볼 수 있다.

(사실 체스 말인데.. 그냥 영어 말로함;)

unit[1][1] = 1 이라면

horse[1] = { row = 1, col = 1, dir = 어떤 방향, isBottom = true }

(벡터 리스트) over[1] = { 1, 위에 있는 말들 없으면 끝 } 

식으로 해당 인덱스를 대입해서 판별하게 해두었다.

vector<int> over[11] 는 위에 쌓이는 말들을 저장하기 위한 리스트로 초기 상태는 자신의 번호만 들어가있다.

ReverseOrder 또는 Move 시에 다른 말위에 올라탈 수 있다면 해당 리스트가 복사되는 형태이다.

ProcessFromColor 로직은 길긴한데.. 이렇게 생겼다.

1. 방향에 맞게 새로운 좌표를 지정 (d, newRow, newCol 설정)

2. 해당 좌표가 IsOutOfBound 라면 방향을 전환 후 이동할 수 있는지 다시 해본다.

(재귀 함수를 이용했는데 step이 0이 아니라면 이미 한번 방향을 돌린 것이고, 그래도 이동이 안되면 가만있는다.)

3. 이동한 곳의 map 정보 판별 ( switch (map[newRow][newCol] )

 3-1. (빨간 칸) ReverseOrder를 통해 뒤집어 주고, 새로운 맨 밑이 현재 인덱스로 설정하게 해주었다.

   이 함수에서 unit[row][col] 에 대한 말 번호, 맨 밑에 있던 말의 isBottom, 새로운 맨 밑이 된 말의 isBottom

   초기화가 굉장히 중요하다. 순서 바꾸는 건 for에 있음.

 3-2. (파란 칸) 방향 전환 후 이동인데, 이미 방향을 바꿨던 경우 (step > 0) 라면 그냥 가만있으면 된다.

 3-3. (하얀 칸) 이동한다. 이동 시 이동할 unit 배열을 통해 말이 있는지 없는지 판별한다.

                   기존 말이 없다면 이동한 말이 해당 좌표에 등록되면 되고,

                   기존 말이 있다면 그 말의 맨 위로 올려버리고 운명을 함께 하면 되겠다.

사실 부족한 코드지만 글을 쓰고, 정리하다보면 좀 더 나아지지 않을까 하는 생각으로 올려봅니다.