[2020 CPC] 2020 중앙대학교 프로그래밍 경진대회 풀이

 

올해 cpc 사진은 아닙니다

 

2020 CPC 중앙대학교 프로그래밍 경진대회 풀이입니다.
웹 공부를 하느라 잠시 쉬고있던 알고리즘을 다시 시작했습니다.
곧 다가오는 2020 인하대학교 IUPC를 대비입니다. 시간내어 푸느라 아직 모든 문제를 풀이하진 못했습니다.
미풀이 문제는 푸는 대로 업데이트 하도록 하겠습니다.

 

 

A. #20205 교수님 그림이 깨지는데요?

www.acmicpc.net/problem/20205

20205번: 교수님 그림이 깨지는데요?

알고리즘 : 단순구현

풀이랄 것이 없습니다. 기본적인 제공문제

출력형식에 띄어쓰기 안 넣어서 실수로 틀린..ㅎㅎ

 

< CODE >

#include <iostream>

using namespace std;

bool pix[105][105];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n,k;
	
	cin >> n >> k;
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			bool chk;
			
			cin >> chk;
			
			for(int a = i*k; a < i*k+k; a++)
				for(int  b = j*k; b < j*k + k; b++)
					pix[a][b] = chk;					
		}
	}
	
	for(int i = 0; i < n*k; i++)
	{
		for(int j = 0; j < n*k; j++)
		{
			cout << pix[i][j] << ' ';
		}
		
		cout << '\n';
	}
    
    return 0;
}

 

B. #20206 푸앙이가 길을 건너간 이유

www.acmicpc.net/problem/20206

20206번: 푸앙이가 길을 건너간 이유

알고리즘 : 수학

등호를 부등식으로 바꿔 영역안에 모든 점이 있는 지 확인하면 됩니다.

문자열 출력문제는 출력 문자열을 배열에 저장해두면 실수를 피할 수 있습니다.

 

 

 

 

 

 

< CODE >

#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>

using namespace std;

string ans[] = {"Poor", "Lucky"};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int a,b,c;
	
	cin >> a >> b >> c;
	
	int x1, x2, y1, y2;
	
	vector<pair<int,int>> dots;
	
	cin >> x1 >> x2 >> y1 >> y2;
	
	dots.push_back({x1,y1});
	dots.push_back({x1,y2});
	dots.push_back({x2,y1});
	dots.push_back({x2,y2});
	
	int chk[2] = {0,};
		
	for(int i = 0; i < dots.size(); i++)
	{
		if(dots[i].first * a + dots[i].second * b <= -c)
			chk[0]++;
		if(dots[i].first * a + dots[i].second * b >= -c)
			chk[1]++;
	}
	
	if(chk[0] == 4 || chk[1] == 4)
		cout << ans[1];
	else
		cout << ans[0];
	
	return 0;
}

 

 

 

C. #20207 달력

www.acmicpc.net/problem/20207

20207번: 달력

알고리즘 : 정렬, 배열

정렬조건함수를 사용하는 법을 알면 쉽게 풀이할 수 있습니다.

 

 

 

 

< CODE >

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

struct sc
{
	int start;
	int end;
};

sc sche[1005];
bool chk[1005][370];
int maxHeight[370];

queue<pair<int,int>> startPoint;
queue<pair<int,int>> q;

int dy[] = {0,-1,0,1};
int dx[] = {1,0,-1,0};

bool operator<(const sc & a, const sc & b)
{
	if(a.start == b.start)
		return a.end > b.end;
	return a.start < b.start;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	
	cin >> n;
	
	for(int i = 0; i < n; i++)
		cin >> sche[i].start >> sche[i].end;
	
	sort(sche,sche+n);
	
	for(int i = 0; i < n; i++)
	{
		sc now = sche[i];
		int height = 1;
		
		while(height <= n)
		{
			if(chk[height][now.start])
				height++;
			else
				break;
		}
		
		for(int j = now.start; j <= now.end; j++)
		{
			chk[height][j] = true;			
			maxHeight[j] = max(maxHeight[j], height);
		}
	}
	
	int result = 0;

	int maxH = 0;
	int l = 0;
	
	for(int i = 1; i <= 365; i++)
	{
		if(maxHeight[i] != 0)
		{
			l++;
			maxH = max(maxHeight[i],maxH);
		}
		else
		{
			result += maxH * l;
			maxH = 0;
			l = 0;
		}
	}
	
	result += maxH * l;
	
	cout << result << '\n';
}

 

 

 

 

 

D. #20208 진우의 민트초코우유

www.acmicpc.net/problem/20208

20208번: 진우의 민트초코우유

알고리즘 : 비트마스크/Brute Force

우유가 10개이므로 우유를 먹는 순열은 10! 개입니다. 10!개를 비트마스크로 관리하고

각 우유간의 거리를 갈 수 있는 지 확인하면 풀이할 수 있습니다.

 

 

 

 

< CODE >

#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int n,m,h;
vector<pair<int,int>> vMilk;
pair<int,int> house;
int result = 0;

int addMilk(const int & bit, int idx)
{
	return bit | (1 << idx);
}

int countMilk(const int & bit)
{
	int ret = 0;
	
	for(int i = 0; i < vMilk.size(); i++)
		if(bit & (1 << i))
			ret++;
	
	return ret;
}

//디버깅 용 함수
void printMilk(int bit)
{
	vector<bool> b;
	
	while(bit > 0)
	{
		b.push_back(bit % 2);
		bit /= 2;
	}
	
	for(int i = b.size() - 1; i >= 0; i--)
		cout << b[i];
	
	cout << '\n';
}

int dist(const pair<int, int> &a, const pair<int,int> &b)
{
	return abs(a.first - b.first) + abs(a.second - b.second);
}

void dfs(int curBit, int hp, pair<int,int> lPoint)
{
	if(curBit == (1 << vMilk.size()) - 1)
	{
		if(dist(lPoint, house) <= hp)
			result = max(result,(int)vMilk.size());
		return;
	}
	
	for(int i = 0; i < vMilk.size(); i++)
	{
		int d = dist(lPoint, vMilk[i]);
		
		if(d <= hp && !(curBit & (1 << i)))
			dfs(addMilk(curBit,i), hp - d + h, vMilk[i]);
	}
	
	if(dist(lPoint,house) <= hp)
	{
		result = max(result,countMilk(curBit));
		// cout << "#type2 : ";
		// printMilk(curBit);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m >> h;
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			int num;
			
			cin >> num;
			
			if(num > 0)
			{
				if(num == 1)
					house = make_pair(i,j);
				else
					vMilk.push_back({i,j});
			}
		}
	}
	
	dfs(0,m,house);
		
	cout << result << '\n';
	return 0;
}

 

 

 

 

 

E. #20209 스트레이트 스위치 게임

www.acmicpc.net/problem/20209

20209번: 스트레이트 스위치 게임

알고리즘 : 비트마스크/BFS

초기구성은 이전 문제와 비슷하나 더욱 복잡합니다. 한 큐브당 5개의 상태가 존재하고

이는 0~5로 구성됩니다. 그리고 큐브는8개이므로 0이 2진수로 000(2) 4가 2진수로 100(2)인 점을 이용해

한 개의 int형 변수(32bit)를 3자리씩 쪼개서 000/000/000/000/000/000/000/000로 8개의 큐브 상태를 나타내는

배열로 사용했습니다. (지금 생각해도 괜히 어렵게 푼 것 같습니다.)

중반까지 DFS로 풀다가 잘 못 풀었음을 깨닫고 리팩토링 하였습니다..ㅠㅠ

 

 

 

 

 

 

< CODE >

#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;

#define MAX 10

int n,k;
int result = 987654321;
vector<int> join[MAX];
queue<pair<int,int>> q;

bool visit[1 << 25];

int getValue(int idx, const int & bit)
{
	int slice = (int)pow(8, idx);
	int ret = (bit % slice) / (slice >> 3);
	
	return ret;
}

bool isComplete(int bit)
{
	int first = bit % 8;
	int idx = 2;
	int slice = 64;
	int value = 0;
	
	while(idx <= n)
	{
		value = (bit % slice) / (slice >> 3);
		
		if(value != first)
			return false;
		
		idx++;
		slice <<= 3;
	}
	
	return true;
}

inline void addNum(int idx, int & bit)
{
	bit += (1 << ((idx - 1) * 3));
	
	if(getValue(idx,bit) >= 5)
		bit -= (5 << ((idx - 1) * 3));
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int sBit = 0;
	
	cin >> n >> k;
	
	for(int i = 1; i <= n; i++)
	{
		int num;
		
		cin >> num;
		
		for(int j = 0; j < num; j++)
			addNum(i, sBit);
	}
	
	for(int i = 1; i <= k; i++)
	{
		int amount;
		
		cin >> amount;
		
		for(int j = 0; j < amount; j++)
		{
			int num;
			
			cin >> num;
			
			join[i].push_back(num);
		}
	}
	
	if(n == 1 || isComplete(sBit))
		cout << "0\n";
	else
	{
		q.push({sBit,0});
		
		while(!q.empty())
		{
			pair<int,int> here = q.front(); q.pop();
			int now = here.first;
			int cnt = here.second;
			
			if(visit[now] || cnt >= result)
				continue;

			visit[now] = true;

			if(isComplete(now))
			{
				result = min(result, cnt);
				continue;
			}

			for(int i = 1; i <= k; i++)
			{
				int temp = now;

				for(int c = 0; c < i; c++)
				{
					for(int j = 0; j < join[i].size(); j++)
						addNum(join[i][j],temp);
				}

				if(isComplete(temp))
				{
					result = min(result, cnt + 1);
					continue;
				}

				q.push({temp, cnt + 1});
			}
		}
	
		if(result == 987654321)
			cout << "-1\n";
		else
			cout << result << '\n';
	}
	
	return 0;
}

 

 

 

 

F. #20210 파일 탐색기

www.acmicpc.net/problem/20210

20210번: 파일 탐색기

알고리즘 : 정렬구현

수많은 런타임에러를 접한 문제입니다.. 처음 접해보는 오류였고 해결하는데 구글링으로 오류를 해결했습니다.

 

코드는 너무 더럽게 짜서 나중에 한 번 수정이 필요할 것 같습니다.

오류는 다음과 같습니다. 72%에서 자꾸 런타임에러가 뜨길래 파일명에 같은 값을 넣고 (같은 파일명이 존재 가능하므로)

n을 바꿔가며 값을 넣었더니 17부터 세그멘테이션 오류가 떠 찾아보다보니 std::sort 함수는 n에 따라서 소팅함수를

유동적으로 변경하는데 n이 커짐에 따라서 compare 함수가 모든 값을 true를 반환할 경우 생기는 오류라고 합니다.

하단 블로그를 통해 오류를 해결하였습니다. 

 

codingdog.tistory.com/entry/c-sort-의-비교함수가-true만-리턴할-때-어떤-일이-일어날까요

 

c++ sort 의 비교함수가 true만 리턴할 때 어떤 일이 일어날까요?

 

< CODE >

#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <string.h>
#include <cstdlib>

using namespace std;

vector<string> v;
map<char,int> m;
map<string,int> sCnt;

void init()
{
	int cnt = 10;
	
	for(char c = 'A'; c <= 'Z'; c++)
	{
		m[c] = cnt;
		cnt += 2;
	}
	
	cnt = 11;
	
	for(char c = 'a'; c <= 'z'; c++)
	{
		m[c] = cnt;
		cnt += 2;
	}
	
	for(char c = '0'; c <= '9'; c++)
		m[c] = (c - '0');
}

int zeroCount(const string & s)
{
	int idx = 0;
	
	while(idx < s.length() && s[idx] == '0')
		idx++;
	
	return idx;
}

int compareBigInteger(string a, string b)
{
	int zCnt1 = zeroCount(a), zCnt2 = zeroCount(b);
	
	int dist = a.length() - b.length();
	int gap = abs(dist);
	
	if(a.length() > b.length())
		for(int i = 0; i < gap; i++)
			b = '0' + b;
	else if(a.length() < b.length())
		for(int i = 0; i < gap; i++)
			a = '0' + a;
	
	for(int i = 0; i < a.length(); i++)
	{
		if(a[i] < b[i])
			return true;
		else if(a[i] > b[i])
			return false;
	}
	
	if(zCnt1 == zCnt2)
		return -1;
	
	return zCnt1 < zCnt2;
}

bool isCharNum(char c)
{
	if(c >= '0' && c <= '9')
		return true;
	return false;
}

bool cmp(const string & a, const string & b)
{
	int curIdx = 0;
	int idx;
	int lnA, lnB;
	
	while(true)
	{
		idx = curIdx;
		lnA = -1, lnB = -1;

		if(a.length() <= idx)
			return true;
		else if(b.length() <= idx)
			return false;
		
		while(a[idx] == b[idx])
		{
			if((idx == curIdx || idx != curIdx && a[idx - 1] > '9') && isCharNum(a[idx]))
				lnA = idx;
			else if(a[idx] > '9')
				lnA = -1;

			if((idx == curIdx || idx != curIdx && b[idx - 1] > '9') && isCharNum(b[idx]))
				lnB = idx;
			else if(b[idx] > '9')
				lnB = -1;

			idx++;

			if(idx >= a.length() || idx >= b.length())
			{
				if(lnA != -1 && lnB != -1)
					break; // 둘다 끝이 숫자면 그냥 진행
				else
					return a.length() < b.length();
			}
		}

		if(lnA == -1 && isCharNum(a[idx]) && lnB == -1 && isCharNum(b[idx]))
		{
			lnA = idx;
			lnB = idx;
		}

		if(a[idx] != b[idx])
		{
			if(lnA != -1 && lnB != -1)
			{
				int ret = -1;

				string tempA, tempB;
				int idx1,idx2;

				for(idx1 = lnA; a[idx1] >= '0' && a[idx1] <= '9'; idx1++)
					tempA += a[idx1];

				for(idx2 = lnB; b[idx2] >= '0' && b[idx2] <= '9'; idx2++)
					tempB += b[idx2];

				ret = compareBigInteger(tempA,tempB);

				if(ret == -1)
				{	
					if(a.length() == idx1)
						return true;
					else if(b.length() == idx2)
						return false;

					curIdx = idx1;
					continue;
				}

				return ret;
			}
			else
				return m[a[idx]] < m[b[idx]];
		}
		else
			return true;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	
	cin >> n;
	
	for(int i = 0; i < n; i++)
	{
		string str;
		
		cin >> str;
		
		
		if(sCnt[str])
			sCnt[str] += 1;
		else
		{
			v.push_back(str);
			sCnt[str] = 1;
		}
	}
	
	init();

	if(v.size() != 1)
		sort(v.begin(), v.end(),cmp);
	
	for(int i = 0; i < v.size(); i++)
		for(int j = 0; j < sCnt[v[i]];j++)
			cout << v[i] << '\n';
	
	return 0;
}

 

다음 문제들은 해결되는 대로 풀이하겠습니다.

 

#2020 중앙대 알고리즘 대회 #2020 CPC #알고리즘 #BOJ 20205 #BOJ 20206 #BOJ 20207 #BOJ 20208 #BOJ 20209

#BOJ 20210 #BOJ 20211 #BOJ 20212