언제나 처음처럼

[문제 링크]

2차원 DP 문제였지만 3차원 DP로 풀어서 코드가 복잡해졌다.

N번째 집의 경우 1번째 집의 색깔과 겹치면 안되기 때문에 이 조건을 처리하기 위해 1차원 더 추가해서 첫번째 집에 어떤 색깔을 칠했는지 캐싱했는데, 2차원 배열로 선언한 뒤 첫번째 집을 R, G, B 각각 칠했을 경우에 대해 각각 DP 로직을 수행해서 그중 가장 비용이 작은 값을 구해도 된다. 2차원 배열로 선언하는 방식이 캐싱하는데 필요한 메모리를 절약할 수 있다.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define INF 987654321
int memo[1000][3][3];

void bottomup(vector<vector<int>>& costs, int N)
{
    int R = 0;
    int G = 1;
    int B = 2;
    
    memo[0][R][R] = costs[0][R];
    memo[0][G][G] = costs[0][G];
    memo[0][B][B] = costs[0][B];
    
    for(int i=1; i<N; i++)
    {
        if(i + 1 == N)
        {
            memo[i][R][G] = min(memo[i-1][R][R], memo[i-1][R][B]) + costs[i][G];
            memo[i][R][B] = min(memo[i-1][R][R], memo[i-1][R][G]) + costs[i][B];

            memo[i][G][R] = min(memo[i-1][G][G], memo[i-1][G][B]) + costs[i][R];
            memo[i][G][B] = min(memo[i-1][G][R], memo[i-1][G][G]) + costs[i][B];

            memo[i][B][R] = min(memo[i-1][B][G], memo[i-1][B][B]) + costs[i][R];
            memo[i][B][G] = min(memo[i-1][B][R], memo[i-1][B][B]) + costs[i][G];
        }
        else 
        {
            memo[i][R][R] = min(memo[i-1][R][G], memo[i-1][R][B]) + costs[i][R];
            memo[i][R][G] = min(memo[i-1][R][R], memo[i-1][R][B]) + costs[i][G];
            memo[i][R][B] = min(memo[i-1][R][R], memo[i-1][R][G]) + costs[i][B];

            memo[i][G][R] = min(memo[i-1][G][G], memo[i-1][G][B]) + costs[i][R];
            memo[i][G][G] = min(memo[i-1][G][R], memo[i-1][G][B]) + costs[i][G];
            memo[i][G][B] = min(memo[i-1][G][R], memo[i-1][G][G]) + costs[i][B];
            
            memo[i][B][R] = min(memo[i-1][B][G], memo[i-1][B][B]) + costs[i][R];
            memo[i][B][G] = min(memo[i-1][B][R], memo[i-1][B][B]) + costs[i][G];
            memo[i][B][B] = min(memo[i-1][B][R], memo[i-1][B][G]) + costs[i][B];
        }
    }
    
    int result = INF;
    for(int first = R; first<=B; ++first)
    {
        for(int here = R; here<=B; ++here)
        {
            if(here==first) continue;
            result = min(result, memo[N-1][first][here]);
        }
    }
    
    cout << result;
}

int main(void)
{
    fill_n(memo[0][0], 1000*3*3, INF);
    
    int N;
    cin >> N;
    
    vector<vector<int>> costs(N, vector<int>(3));
    
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<3; ++j)
        {
            cin >> costs[i][j];
        }
    }
    
    bottomup(costs, N);
    
    return 0;
}

[문제 링크]

간단한 DP 문제였다.

자신의 차례에서 1개나 3개를 가져갔을 때 상대방이 승리하는지 여부는 가져간 개수에서 상대방이 1개나 3개를 가져갔을 때 자신이 승리하는지 여부에 결정된다. 그리고 이것을 계속 반복하다가 결국 기저사례 (N=1, N=2, N=3)에 도달하게 되면 최종적으로 승리와 패배가 결정되게 된다. 점화식은 다음과 같다.

Dp(N) = !(DP(N-1) || DP(N-3))

참고로 이 문제는 베스킨라빈스31 게임처럼 규칙 상 무조건 승리하는 필승법이 있다. 짝수개가 남도록 가져가면 결국 상대방이 패배한다. 즉 N이 홀수면 상근이가 이기고, 짝수면 창영이 이기게 된다.

#include <iostream>
using namespace std;

bool memo[1001] = {false,};
bool visited[1001] = {false,};

bool Topdown(int remain)
{
    if(remain == 1 || remain == 3)
    {
        return true;
    }   
    else if(remain == 2)
    {
        return false;
    }
    
    if(visited[remain]) 
    {
        return memo[remain];        
    }
    
    visited[remain] = true;
    
    return memo[remain] = !(Topdown(remain-1) || Topdown(remain-3));
}

bool Bottomup(int remain)
{
    memo[1] = true;
    memo[2] = false;
    memo[3] = true;
    
    for(int i = 4; i<=remain; ++i)
    {
        memo[i] = !(memo[i-1] || memo[i-3]);
    }
    
    return memo[remain];
}

int main(void)
{
    int N;
    cin >> N;
    
    if(Topdown(N))
    {
        cout << "SK";
    }   
    else 
    {
        cout << "CY";
    }
    
    return 0;
}

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

간단한 BFS 문제였다.

물높이가 0에서부터 지역 중 최고 높은 지역의 높이까지 경우에서 안전 영역의 개수를 계산하여 가장 많은 안전 영역의 개수를 출력해주면 된다.

안전 영역의 개수는 물높이보다 높은 지역을 시작으로 인접한 칸에 물높이보다 높은 지역이 있는지 탐색하는 BFS를 수행하면서 방문체크를 하고, 모든 좌표를 탐색했을 때 수행한 BFS 탐색의 수가 곧 안전 영역의 개수가 된다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int getMaxSafeAreaCount(const vector<vector<int>>& cityArr, int RainHeight)
{
	int N = cityArr.size();
	vector<vector<bool>> visited(N, vector<bool>(N, false));

	int safeAreaCount = 0;

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

	for(int y=0; y<N; y++)
		for (int x = 0; x < N; x++)
		{
			if (visited[y][x] || cityArr[y][x] <= RainHeight)
				continue;

			safeAreaCount++;

			queue<pair<int, int>> q;
			q.push({ y,x });
			visited[y][x] = true;

			while (!q.empty())
			{
				int hereY = q.front().first;
				int hereX = q.front().second;
				q.pop();

				for (int i = 0; i < 4; i++)
				{
					int nextY = hereY + dy[i];
					int nextX = hereX + dx[i];

					if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < N)
					{
						if (!visited[nextY][nextX] && cityArr[nextY][nextX] > RainHeight)
						{
							q.push({ nextY, nextX });
							visited[nextY][nextX] = true;
						}
					}
				}

			}
		}

	return safeAreaCount;
}

int main(void)
{
	int N;
	cin >> N;

	vector<vector<int>> cityArr(N, vector<int>(N));

	int maxHeight = 0;

	for(int y=0; y<N; y++)
		for (int x = 0; x < N; x++)
		{
			cin >> cityArr[y][x];
			maxHeight = max(maxHeight, cityArr[y][x]);
		}

	int maxSafeAreaCount = 0;

	for (int i = 0; i < maxHeight; i++)
	{
		maxSafeAreaCount = max(maxSafeAreaCount, getMaxSafeAreaCount(cityArr, i));
	}

	cout << maxSafeAreaCount;

	return 0;
}

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

간단한 구현 문제였다.

최종 인원이 1명이 될 때 까지 라운드를 반복하다가

매치 트리에서 왼쪽에 있는 참가자 번호와 오른쪽에 있는 참가자 번호가 지민, 한수 번호와 일치한다면 해당 라운드 값을 출력해주면 된다.

#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
	int jiminNum;
	int hansuNum;
	int maxNum;

	cin >> maxNum;
	cin >> jiminNum;
	cin >> hansuNum;

	int round = 0;
	bool isMatching = false;

	while (maxNum > 1 && !isMatching)
	{
		round++;

		int matchNum = 0;

		for (int i = 1; i <= maxNum; i += 2)
		{
			matchNum++;

			int leftNum = i;
			int rightNum = i + 1;

			if (leftNum == jiminNum || rightNum == jiminNum)
			{
				jiminNum = matchNum;

				if (rightNum == hansuNum || leftNum == hansuNum)
				{
					isMatching = true;
					break;
				}
			}
			else if (leftNum == hansuNum || rightNum == hansuNum)
			{
				hansuNum = matchNum;
			}
		}

		maxNum = matchNum * 2 < maxNum ? matchNum + 1 : matchNum;
	}

	if (isMatching)
		cout << round;
	else
		cout << -1;

	return 0;
}

[문제 링크]

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

문자열을 이용하는간단한 구현 문제였다.

등급에 따른 과목평점을 Map 컨테이너에 담아서 간단하게 매칭시켰다.

#include <iostream>
#include <string>
#include <map>
using namespace std;

void gradeMapping(map<string, float>& gradeScoreMap) {
	gradeScoreMap["A+"] = 4.5f;
	gradeScoreMap["A0"] = 4.0f;
	gradeScoreMap["B+"] = 3.5f;
	gradeScoreMap["B0"] = 3.0f;
	gradeScoreMap["C+"] = 2.5f;
	gradeScoreMap["C0"] = 2.0f;
	gradeScoreMap["D+"] = 1.5f;
	gradeScoreMap["D0"] = 1.0f;
	gradeScoreMap["F"] = 0.0f;
}

int main(void) {
	map<string, float> gradeScoreMap;
	gradeMapping(gradeScoreMap);

	float credit = 0;
	float totalCredit = 0;

	for (int i = 0; i < 20; i++) {
		string subjectStr, creditStr, gradeStr;
		cin >> subjectStr >> creditStr >> gradeStr;
		if (gradeStr == "P")
			continue;
		else {
			float nowCredit = stof(creditStr);
			float nowGrade = gradeScoreMap[gradeStr];
			credit += nowCredit;
			totalCredit += nowCredit * nowGrade;
		}
	}

	cout << totalCredit / credit << endl;

	return 0;
}

[문제 링크]

https://onlytrying.tistory.com/229    

예전에 풀었던 토마토 문제와 동일한 문제였다.

차이점은 상자의 상태가 3차원 배열이라는 점이다.

따라서, 기존의 구현 코드에서 상자를 3차원 배열로 변경하고 Z 좌표가 바뀌는 경우를 추가해주었다.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

struct boxPos {
	int z, y, x;
};

int M, N, H;
int box[101][101][101];
queue<boxPos> ripeTomatoPosQ;
int dz[6] = { 0,0,0,0,1,-1 };
int dy[6] = { 0,0,1,-1,0,0 };
int dx[6] = { 1,-1,0,0,0,0 };

int getDay(int unripeTomato) {
	int day = 0;

	while (unripeTomato > 0) {
		day++;

		int newRipeTomatoCnt = ripeTomatoPosQ.size();
		// 안익은 토마토가 남아있는 상태에서 새롭게 익은 토마토가 없다면 토마토를 모두 익히는건 불가능하다.
		if (newRipeTomatoCnt == 0)
			return -1;

		for (int i = 0; i < newRipeTomatoCnt; i++) {
			int hereZ = ripeTomatoPosQ.front().z;
			int hereY = ripeTomatoPosQ.front().y;
			int hereX = ripeTomatoPosQ.front().x;
			ripeTomatoPosQ.pop();

			// 주변의 토마토를 익힌다.
			for (int i = 0; i < 6; i++) {
				int nearZ = hereZ + dz[i];
				int nearY = hereY + dy[i];
				int nearX = hereX + dx[i];

				if (nearZ >= 0 && nearZ < H && nearY >= 0 && nearY < N && nearX >= 0 && nearX < M)
					if (box[nearZ][nearY][nearX] == 0) {
						// 안익은 토마토를 익은 토마토로 바꾸고 안익은 토마토의 갯수를 1 감소시킨다.
						box[nearZ][nearY][nearX] = 1;
						unripeTomato--;

						// 새롭게 익은 토마토의 좌표를 큐에 담는다.
						ripeTomatoPosQ.push({ nearZ, nearY, nearX });
					}
			}
		}
	}

	return day;
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	cin >> M >> N >> H;

	int unripeTomato = 0;
	for (int z = 0; z < H; z++) {
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				int state;
				cin >> state;
				box[z][y][x] = state;
				if (state == 0)
					unripeTomato++;
				else if (state == 1)
					ripeTomatoPosQ.push({ z,y,x });
			}
		}
	}

	cout << getDay(unripeTomato) << endl;

	return 0;
}

[문제 링크]

문자열과 관련된 구현 문제였다.

문자열의 길이가 최대 100,000이기 때문에 뒤집기 연산을 할 때 실제 문자열을 뒤집으면 시간 복잡도가 너무 커지게 된다.

따라서 뒤집기 연산을 할 때마다 isReversed 변수를 토글하여 현재 뒤집힌 상태인지 아닌지를  저장하고,

버리기 연산을 하게 될 경우 현재 뒤집히지 않은 상태라면 앞에서 숫자를 빼고, 뒤집힌 상태라면 뒤에서 숫자를 빼는 방식으로 구현하였다.

앞, 뒤에서 자유롭게 원소를 넣고 빼는 연산을 수행하기 위해 자료구조는 Deque를 사용하였다.

마지막으로 문자열을 출력하는 연산에서는

뒤집히지 않은 상태라면 Deque의 앞에서부터 하나씩 그대로 출력해주면 되며,

뒤집힌 상태일 경우 Deque의 뒤에서부터 하나씩 빼는데 그대로 출력하면 숫자가 뒤집혀서 출력되기 때문에 숫자를 임시로 저장하는 Stack 컨테이너에 옮겨 담아서 출력하였다.

#include <iostream>
#include <vector>
#include <stack>
#include <deque>
using namespace std;

void printAC(string acStr, string func) {
	deque<char> dq;
	for (auto x : acStr)
		dq.push_back(x);

	dq.pop_front();
	dq.pop_back();

	bool isReversed = false;

	for (auto x : func) {
		if (x == 'R')
			isReversed = !isReversed;
		else {
			if (dq.empty()) {
				cout << "error";
				return;
			}

			char hereChar;
			if (!isReversed) {
				hereChar = dq.front();
				dq.pop_front();

				while (!dq.empty() && hereChar != ',') {
					hereChar = dq.front();
					dq.pop_front();
				}

			}
			else {
				hereChar = dq.back();
				dq.pop_back();

				while (!dq.empty() && hereChar != ',') {
					hereChar = dq.back();
					dq.pop_back();
				}

			}
		}
	}

	char hereChar;

	cout << '[';
	if (!isReversed) {
		while (!dq.empty()) {
			hereChar = dq.front();
			dq.pop_front();

			cout << hereChar;
		}
	}
	else {
		stack<char> tempStk;
		while (!dq.empty()) {
			hereChar = dq.back();
			dq.pop_back();

			if (hereChar != ',')
				tempStk.push(hereChar);
			else {
				while (!tempStk.empty()) {
					cout << tempStk.top();
					tempStk.pop();
				}
				cout << hereChar;
			}
		}
		while (!tempStk.empty()) {
			cout << tempStk.top();
			tempStk.pop();
		}
	}
	cout << ']';
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int tc;
	cin >> tc;

	while (tc--) {
		string func;
		cin >> func;

		int n;
		cin >> n;

		string acStr;
		cin >> acStr;

		printAC(acStr, func);
		cout << '\n';
	}

	return 0;
}

[문제 링크]

N과 M의 최댓값이 500,000으로 매우 크기 때문에 일반적인 탐색으로는 제한 시간내에 정답을 구할 수 없다.

따라서 이분 탐색으로 원소를 찾도록 구현해야 한다.

c++ STL에 정의된 Set 컨테이너를 사용하면 쉽게 구현할 수 있다.

Set 컨테이너는 균형 이진 트리로 구현되어 있으므로 원소를 추가하면 자동으로 정렬되며, 원소를 로그 시간으로 찾을 수 있다는 특징이 있다.

Set을 통해 구현하는 것과 이분 탐색을 직접 구현하는 것 두가지 방법으로 구현하였다.

<Set 컨테이너 사용>

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main(void) {
	int N, M;
	cin >> N >> M;

	set<string> personSet;
	while (N--) {
		string str;
		cin >> str;
		personSet.insert(str);
	}	

	vector<string> result;
	while (M--) {
		string str;
		cin >> str;

		set<string>::iterator iter = personSet.find(str);
		if (iter != personSet.end())
			result.push_back(*iter);
	}

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

	cout << result.size() << '\n';
	for (auto x : result)
		cout << x << '\n';

	return 0;
}

<Binary_search & sort 직접 구현>

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

void swap(vector<string>& v, int idx1, int idx2) {
	string temp = v[idx1];
	v[idx1] = v[idx2];
	v[idx2] = temp;
}
void swap(int arr[], int idx1, int idx2) {
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}

int getMidIndex(vector<string>& v, int start, int end) {
	int mid = (start + end) / 2;
	int idx[3] = { start, mid, end };

	if (v[idx[0]] > v[idx[1]])
		swap(idx, 0, 1);
	if (v[idx[1]] > v[idx[2]])
		swap(idx, 1, 2);
	if (v[idx[0]] > v[idx[1]])
		swap(idx, 0, 1);

	return idx[1];
}

void quick_sort(vector<string>& v, int left, int right) {
	if (left >= right) return;

	int pIdx = getMidIndex(v, left, right);
	swap(v, left, pIdx);

	int pivot = left;
	int low = left + 1;
	int high = right;

	while (true) {
		while (low <= right && v[low] <= v[pivot])
			low++;
		while (high > left && v[high] >= v[pivot])
			high--;

		if (low > high)
			break;
		
		swap(v, low, high);
	}

	swap(v, pivot, high);
	quick_sort(v, left, high - 1);
	quick_sort(v, high + 1, right);
}

bool binary_search(vector<string>& personVector, string str) {
	int start = 0;
	int end = personVector.size() - 1;

	while (start <= end) {
		int mid = (start + end) / 2;

		if (personVector[mid] == str)
			return true;
		else if (personVector[mid] < str)
			start = mid + 1;
		else
			end = mid - 1;
	}

	return false;
}

int main(void) {
	int N, M;
	cin >> N >> M;

	vector<string> personVector;
	while (N--) {
		string str;
		cin >> str;
		personVector.push_back(str);
	}	
	quick_sort(personVector, 0, personVector.size() - 1);

	vector<string> result;
	while (M--) {
		string str;
		cin >> str;

		if (binary_search(personVector, str)) {
			result.push_back(str);
		}
	}
	quick_sort(result, 0, result.size() - 1);

	cout << result.size() << '\n';
	for (auto x : result)
		cout << x << '\n';

	return 0;
}