Mist16's Dev Blog

문제

• 1007번 : 벡터 매칭
• Rank : Gold II
• 링크 : https://www.acmicpc.net/problem/1007

풀이 전략

• 평면상의 점들을 두개씩 짝지어 벡터를 만들고, 그 벡터들의 합을 구한 후 길이로 변환한다.
• 다만, 브루트포스로 for문을 돌릴 경우 N! 만큼의 계산이 필요하여 시간제한에 맞출 수 없다.
• V1 + V2 + V3 + V4 + .... = (a1-b1) + (a2 - b2) + ... = (a1 + b1 - b1 - b1).... 이므로
  • 벡터들의 합 = (전체 좌표의 합) - 2 * (점 절반의 합)이 된다.
• 해당 방법을 사용하여, N개의 점 중 N/2개의 점을 도출해낸 뒤, 벡터 길이의 최소값을 구하는 방법으로 풀이한다.
  • for문 대신 재귀함수를 사용하여 현재 인덱스 / 선택해야 하는 점의 개수를 인자로 사용하는 방식으로 구현하였다. N의 최대값이 20이었으니 비트마스킹을 사용해도 괜찮았을 듯.

	void pick(int left, int currentIdx, long long vectorX, long long vectorY)
	{
		if (left == 0)
		{
			long long X = totalX - vectorX - vectorX;
			long long Y = totalY - vectorY - vectorY;
			unsigned long long temp = (X * X) + (Y * Y);
			if (temp < MinValue)
			{
				MinValue = temp;
			}
			return;
		}
		if (currentIdx >= N)
			return;
		pick(left, currentIdx + 1, vectorX, vectorY);
		pick(left - 1, currentIdx + 1, vectorX + pos[currentIdx][0], vectorY + pos[currentIdx][1]);
	}

전체 소스 코드

//Backjoon Problem No.1007
//https://www.acmicpc.net/problem/1007
//Mist16, 2022-01-24
#include <iostream>
#include <limits>
#include <math.h>

using namespace std;

class VectorMatching
{
private:
	int N;
	int pos[20][2];
	long long totalX;
	long long totalY;
	unsigned long long MinValue;
public:
	VectorMatching()
	{
		N = 0;
		MinValue = 0xffffffffffffffff;
		totalX = 0;
		totalY = 0;
	}

	void input()
	{
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			cin >> pos[i][0] >> pos[i][1];
			totalX += pos[i][0];
			totalY += pos[i][1];
		}
	}

	void Run()
	{
		pick(N / 2, 0, 0, 0);
		long double temp = sqrtl(MinValue);
		cout.precision(16);
		cout << temp << endl;
	}

	void pick(int left, int currentIdx, long long vectorX, long long vectorY)
	{
		if (left == 0)
		{
			long long X = totalX - vectorX - vectorX;
			long long Y = totalY - vectorY - vectorY;
			unsigned long long temp = (X * X) + (Y * Y);
			if (temp < MinValue)
			{
				MinValue = temp;
			}
			return;
		}
		if (currentIdx >= N)
			return;
		pick(left, currentIdx + 1, vectorX, vectorY);
		pick(left - 1, currentIdx + 1, vectorX + pos[currentIdx][0], vectorY + pos[currentIdx][1]);
	}

};

int main()
{
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int testCases;

	//input n, pipemap;
	cin >> testCases;
	for (int i = 0; i < testCases; i++)
	{
		VectorMatching vMatch;
		vMatch.input();
		vMatch.Run();
	}
	return 0;
}

여담

• 수학적으로 계산을 정리함으로서 계산 단계를 줄일 수 있는 문제였다. 바로 코딩하기보다는, 식을 확인하고 한 번 정리한 뒤 풀이에 들어가는 것이 좋을 듯 하다.
• n개의 수 중 m개를 선택하는 상황에서, for문으로 n회를 돌리는 대신, i번째 수를 넣을지/안 넣을지로 재귀 함수를 사용하는 방법도 괜찮은 것 같다.

문제

• 17070번 : 파이프 옮기기
• Rank : Gold V
• 링크 : https://www.acmicpc.net/problem/17070

풀이 전략

• 파이프는 좌, 하단, 좌하단대각선으로만 움직인다.
  • 파이프라인이 재귀될 염려가 없으므로, 파이프 이동선을 기억할 필요는 없다.
• 모든 경우의 수를 탐색하여, 가능한 경우의 수를 합산한다.

//파이프 설치
int installPipe(int y, int x, int cond)
{
	int AllCases = 0;

	if (x == N-1 && y == N-1)
		return 1;

	if ((checkMap[y][x] & pipeCond::ConditionChecked) != pipeCond::ConditionChecked ) //unchecked, check
	{
		checkConstructProb(y, x);
	}
	//1. Left/LDown -> Left
	if (cond == pipeCond::Left || cond == pipeCond::LDown)
	{
		if((checkMap[y][x] & pipeCond::Left) == pipeCond::Left)
		{
			AllCases += installPipe(y, x + 1, pipeCond::Left);
		}
		
	}
	//2. Down/LDown -> Down
	if (cond == pipeCond::Down || cond == pipeCond::LDown)
	{
		if ((checkMap[y][x] & pipeCond::Down) == pipeCond::Down)
		{
			AllCases += installPipe(y + 1, x, pipeCond::Down);
		}
	}
	//3. All Cond -> LDown
	if ((checkMap[y][x] & pipeCond::LDown) == pipeCond::LDown)
	{
		AllCases += installPipe(y + 1, x + 1, pipeCond::LDown);
	}

	return AllCases;
}

• 이 때, 같은 위치의 파이프 설치여부를 여러번 체크하게 되므로, 다이나믹 프로그래밍으로 풀이한다.
  • enum을 사용하여 각 상태를 정의해둔 후, 비트연산자 배열에 저장한다.
  • 타설가능 파이프 외에 검사했는지 여부를 확인하게 하여, 타설불가능 지역을 계속해서 체크하는 것을 방지한다.

int checkMap[16][16] = { 0, };
enum pipeCond
{
	None = 0,
	Left = 1,
	LDown = 2,
	Down = 4,
	ConditionChecked = 8
};
//현재 위치에서 파이프 타설이 가능한지 체크
void checkConstructProb(int y, int x)
{
	int cond = pipeCond::ConditionChecked;
	//1. Left
	if (x + 1 < N)
	{
		if (pipeMap[y][x + 1] == 0)
			cond = cond | pipeCond::Left;
	}
	//2. Down
	if (y + 1 < N)
	{
		if (pipeMap[y + 1][x] == 0)
			cond = cond | pipeCond::Down;
	}
	//3. Left-Down
	if ((cond & pipeCond::Left) == (int)pipeCond::Left &&
		(cond & pipeCond::Down) == (int)pipeCond::Down)
	{
		if (pipeMap[y + 1][x + 1] == 0)
		{
			cond = cond | (int)pipeCond::LDown;
		}
	}
	checkMap[y][x] = cond;
}

전체 소스 코드

//Backjoon Problem No.17070
//Mist16, 2022-01-22

#include <iostream>

using namespace std;

enum pipeCond
{
	None = 0,
	Left = 1,
	LDown = 2,
	Down = 4,
	ConditionChecked = 8
};

int pipeMap[16][16] = { 0, };
int checkMap[16][16] = { 0, };
int N = 0;



//현재 위치에서 파이프 타설이 가능한지 체크
void checkConstructProb(int y, int x)
{
	int cond = pipeCond::ConditionChecked;
	//1. Left
	if (x + 1 < N)
	{
		if (pipeMap[y][x + 1] == 0)
			cond = cond | pipeCond::Left;
	}
	//2. Down
	if (y + 1 < N)
	{
		if (pipeMap[y + 1][x] == 0)
			cond = cond | pipeCond::Down;
	}
	//3. Left-Down
	if ((cond & pipeCond::Left) == (int)pipeCond::Left &&
		(cond & pipeCond::Down) == (int)pipeCond::Down)
	{
		if (pipeMap[y + 1][x + 1] == 0)
		{
			cond = cond | (int)pipeCond::LDown;
		}
	}
	checkMap[y][x] = cond;
}

//파이프 설치
int installPipe(int y, int x, int cond)
{
	int AllCases = 0;

	if (x == N-1 && y == N-1)
		return 1;

	if ((checkMap[y][x] & pipeCond::ConditionChecked) != pipeCond::ConditionChecked ) //unchecked, check
	{
		checkConstructProb(y, x);
	}
	//1. Left/LDown -> Left
	if (cond == pipeCond::Left || cond == pipeCond::LDown)
	{
		if((checkMap[y][x] & pipeCond::Left) == pipeCond::Left)
		{
			AllCases += installPipe(y, x + 1, pipeCond::Left);
		}
		
	}
	//2. Down/LDown -> Down
	if (cond == pipeCond::Down || cond == pipeCond::LDown)
	{
		if ((checkMap[y][x] & pipeCond::Down) == pipeCond::Down)
		{
			AllCases += installPipe(y + 1, x, pipeCond::Down);
		}
	}
	//3. All Cond -> LDown
	if ((checkMap[y][x] & pipeCond::LDown) == pipeCond::LDown)
	{
		AllCases += installPipe(y + 1, x + 1, pipeCond::LDown);
	}

	return AllCases;
}

int main()
{
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//input n, pipemap;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> pipeMap[i][j];
		}
	}
	cout << installPipe(0, 1, pipeCond::Left);

	return 0;
}

여담

• 골드 하위권 문제까지는 빠르게 풀 수 있는 거 같다. 고난이도 문제에 도전해볼 것.

문제

• 1202번 : 보석 도둑
• Rank : Gold II
• 링크

풀이 전략

• 보석의 정보를 담은 구조체를 만들어 list에 입력받은 뒤, price 기준으로 정렬하여 비싼 보석부터 확인하였다.
  • bool operator<(const Jewel s) const를 구현하여 정렬
• 가방의 경우 multiset에 저장한 뒤, lower_bound를 사용하여 비싼 보석부터 하나씩 매칭.
• 보석을 전부 확인하거나, 가방이 가득 찬 경우 종료.

소스 코드

//Backjoon Problem No.1202
//Mist16, 2022-01-21

#include <iostream>
#include <list>
#include <set>
using namespace std;

struct Jewel
{
	int weight;
	int price;
	Jewel(int wei, int pri) : weight(wei), price(pri) {}

	//정렬시 price 기준으로 소트되도록 설정
	bool operator<(const Jewel s) const
	{
		return this->price > s.price;
	}
};

list<Jewel> jewels;
multiset<int> Bags;

int N, K;

int main()
{
	int tempWeight, tempValue;
	long long int totalPrice = 0;
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		cin >> tempWeight >> tempValue;
		jewels.push_back(Jewel(tempWeight, tempValue));
	}
	for (int i = 0; i < K; i++)
	{
		cin >> tempWeight;
		Bags.insert(tempWeight);
	}
	jewels.sort();

	//가장 비싼 보석부터, 가능한한 가장 작은 가방에 적재
	for (auto iter1 = jewels.begin(); iter1 != jewels.end(); iter1++)
	{
		auto iter2 = Bags.lower_bound(iter1->weight);
		if (iter2 != Bags.end())
		{
			totalPrice += iter1->price;
			Bags.erase(iter2);
			//모든 가방이 찼을 경우 종료
			if (Bags.size() == 0)
			{
				cout << totalPrice;
				return 0;
			}
		}
	}
	cout << totalPrice;
	return 0;
}

여담

• 10만 개 이상의, 대량의 데이터를 가공하는 문제에서 자료구조 선택으로 인한 시간 문제가 발생하는 경우가 있다.
  • 각 자료구조별 순차접근/임의접근, 삽입/삭제 효율에 관해 정리해보는것도 좋을 듯.

문제

• 16566번 : 카드 게임
• Rank : Emerald V
• 링크

풀이 전략

• STL::Vector을 사용하여 한번에 입력받은 후 정렬 실행
  
  • 입력 이전에 reserve 공간 확보(대량의 move 실행 방지)
• 카드 입력을 비교하여 상대방의 카드가 MAX 이상, MIN 이하일 경우, 최저 카드를 제출
• 중간값일 경우 이진 검색을 실행하여 해당 카드를 이길 수 있는 카드를 찾아 제출
• 제출 후, 뽑은 카드는 Vector에서 삭제

결과

• 공개Test case, 자체 Test Case는 성공하나, 제출 진행시 시간부족으로 실패 처리
• 백준 테스트 환경에서 대형 케이스(카드 4백만, 뽑을 카드 1만)를 시도할 경우, 시간부족으로 실패하는 것으로 보임.
• Vector 대신 자체 이진 그래프를 작성하여 시도해볼 것

소스 코드

//Backjoon Problem No.16566
//Mist16, 2022-01-21

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

using namespace std;


class cardDeck
{
private:
	vector<int> cardSet;

public:

	void setSize(int num)
	{
		cardSet.reserve(num);
	}
	void insertCard(int num)
	{
		cardSet.push_back(num);
	}

	void sortCards()
	{
		sort(cardSet.begin(), cardSet.end());
	}
    
	void deleteCard(vector<int>::iterator iter)
	{
		cardSet.erase(iter);
	}

	vector<int>::iterator getMinCard()
	{
		auto iter = cardSet.begin();
		return iter;
	}
	vector<int>::iterator getMaxCard()
	{
		auto iter = cardSet.end();
		iter--;
		return iter;
	}

	int popCard(int target)
	{
		vector<int>::iterator popOutCard;
		int outCardNum;
		if (target >= *getMaxCard() || target <= *getMinCard()) //losing hand
		{
			popOutCard = getMinCard();
			outCardNum = *popOutCard;
			deleteCard(popOutCard);
			return outCardNum;
		}
		else
		{
			popOutCard = findCard(target);
			outCardNum = *popOutCard;
			deleteCard(popOutCard);
			return outCardNum;
		}
	}

	vector<int>::iterator findCard(int target)
	{
		auto start = cardSet.begin();
		auto end = cardSet.end() - 1;
		int size = cardSet.size();

		while (1)
		{
			auto middle = start + (size / 2);
			if (size == 1)
			{
				return start;
			}
			size = size - (size / 2);

			if (*middle == target)
			{
				return middle + 1;
			}
			else if (*middle < target)
			{
				start = middle;
				continue;
			}
			else
			{
				end = middle;
				continue;
			}
		}
	}

};

int N, M, K;
cardDeck myDeck;

int main()
{
	int cardNum = 0;

	//입출력 속도 관리용
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> K;

	//reserve 함수를 사용하여, 미리 vector의 공간을 확보해둔다
	myDeck.setSize(M);

	for (int i = 0; i < M; i++)
	{
		cin >> cardNum;
		myDeck.insertCard(cardNum + 1);
	}
	myDeck.sortCards();

	for (int i = 0; i < K; i++)
	{
		cin >> cardNum;
		cout << myDeck.popCard(cardNum) << "\n";
	}
}