이것 저것 &

문제링크:www.acmicpc.net/problem/2529

algorithm 라이브러리에서 제공하는 순열 함수를 사용하여 해결했습니다.

k+1개의 수를 만든 다음 큰 수부터 작은 수순으로, 그리고 작은 수부터 큰 수순으로 차례대로 결과값이 될 수 있는지 확인해주면 결과를 도출했습니다.

처음에 재귀함수로 접근하려고 했는데 생각해보니 굳이 필요없을 것 같습니다. 

아래는 정답코드입니다.

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

int k;
vector <char> arr;
vector <int> val;
bool chk() {

	for (int i = 0; i < arr.size(); i++) {
		if (arr[i] == '<') {
			if (val[i] > val[i + 1])
				return false;
		}
		else {
			if (val[i] < val[i + 1])
				return false;
		}
	}
	return true;
}


int main() {

	cin >> k;
	for (int i = 0; i < k; i++) {
		char temp;
		cin >> temp;
		arr.push_back(temp);
	}
	for (int j = 0, i = 9; j < k + 1; j++,i--) 
		val.push_back(i);
	while (1) {
		if (chk() == true)
			break;
		prev_permutation(val.begin(), val.end());
	}
	for (int i = 0; i < val.size(); i++)
		cout << val[i];
	cout << endl;

	val.clear();
	for (int i = 0; i < k + 1; i++)
		val.push_back(i);

	while (1) {
		if (chk() == true)
			break;

		next_permutation(val.begin(), val.end());
		
	}
	for (int i = 0; i < val.size(); i++)
		cout << val[i];
	cout << endl;
	return 0;

}

문제링크:www.acmicpc.net/problem/12904

(1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

문자열의 범위가 위와 같으므로 재귀함수를 사용해 구현하면 시간 초과입니다.

S를 통해서 T를 만드는데 이때 T를 통해서 S를 유추하면 더욱 쉽다는 것을 아는지 모르는지에 따라서 난이도가 크게 달라지는 문제입니다.

T에서 두가지 규칙에 의해서 S문자열의 길이와 같아지게 될때 까지 반복하면 S를 통해서 T를 만들 수 있는지 여부가 결정되기 때문입니다.

구현자체의 난이도는 하,  문제 해결 아이디어가 중상..

아래는 정답코드입니다. 코드로 보면 충분히 이해가 되실겁니다.

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


string s, t;
bool result = 0;


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

	cin >> s;
	cin >> t;


	while (1) {

		if (s.size() == t.size()) {
			if (s == t)
				result = 1;
			break;
		}
		
		if (t[t.size() - 1] == 'A')
			t.pop_back();
		else {
			t.pop_back();
			reverse(t.begin(), t.end());
		}
	}

	cout << result << endl;
}

문제링크:www.acmicpc.net/problem/2839

레전드 문제 설탕배달입니다....ㅋㅋㅋ

입문자분들이 가장 많이 풀고 절망을 느끼는 문제입니다.

오랜만에 다시 풀어봤는데 감회가 새로워서 포스팅합니다.

저의 예전 답입니다.

#include <stdio.h>
int main()
{
	int x = 0, y = 0, N = 0, resultx = 0, resulty = 0;
	int i = 0;
	int j = 0;
	scanf("%d", &N);
	for (x = 0; i <= N; x++)
	{
		i = 5 * x;
		for (y = 0; j <= N; y++)
		{
			j = 3 * y;
			if (i + j == N)
			{
				resultx = x;
				resulty = y;
			}
		}
		j = 0;
	}
	if (resultx == 0 && resulty == 0)
		printf("%d\n", -1);
	else
		printf("%d\n", resultx + resulty);
}

이중포문을 사용해서 구현했습니다.

5씩 증가하는 i와 3씩 증가하는 j의 모든 조합을 비교해보며 결과값을 도출하는 방법입니다. i가 j보다 상위 반복문에 있기 때문에 i가 최대가 되는 결과값이 최종적으로 resulty, x 에 저장이 되어지고 이를 통해 결과값을 얻습니다.

하지만 만약에 시간이나 데이터 크기가 더욱 커진다면 테스트를 통과하지 못할 확률이 있습니다.

예를 들어서 n=1000,000라면 해당 코드는 O(n^2)이므로 시간제한 1초를 훌쩍 넘게 됩니다.

이를 예방하기 위해서  반복문 하나만 써서 해결하는 방식도 생각해봤습니다.

	int answer = 0;
	int mod, num, result;
	num = n / 5;



	while (num >= 0) {

		mod = 0;
		result = 0;

		if (num > 0) {
			mod = n - 5 * num;
			result = num;
		}
		else {
			mod = n;
		}

		result += mod / 3;
		mod = mod % 3;

		if (mod == 0) {
			answer = result;
			return answer;
		}

		num--;

	}
	if (mod != 0)
		return -1;

	
		
	//return answer;

사실 같은 원리입니다. while문에서 5로 나눌수 있는 만큼 반복하며 진행합니다. 이때 5로 나눈 나머지만큼 3으로 다시한번 나눠보고 나머지가 0된다면 그대로 바로 결과를 출력하는 구조입니다.

사실은 2중포문을 사용할 필요가 없던 코드입니다. 

사실 구현하면서 고민을 꽤 많이 했던터라 아직도 많이 부족하다는 것을 느낄 수 있었습니다. 

더욱 열심히 해서 알고리즘 마스터가 되겠습니다. 

문제링크: acmicpc.net/problem/2116

전형적인 구현문제입니다. 문제를 읽으면서 왤캐어렵지.. 생각했는데 

문제 조건중에 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다 라는 조건이 있어서 금방 접근 방법을 찾았습니다.

첫번째 값에서 시작할때 ~ 여섯번째 값에서 시작할때

총 6가지 경우 전부 확인해주어야 하는 브루트 포스입니다.

이때 1(a)번 위치는 6(f)번 위치와 2(b)번위치는 4(d)번위치와 3(c)번위치는 5(e)번 위치와 짝을 이루게 됩니다.

위아래가 되는 값들은 마킹을 해주고 나머지 값들을 통해서 결과값을 얻으면 됩니다. 

• 1. 위아래 값 마킹 
• 2. 결과값 비교

구현자체 난이도를 요하는 문제인데, 그 마저도 주사위에 익숙하시다면 어렵지 않으셨을 겁니다.

구현 문제는 꼭 설계를 꼼꼼하게 작성하고 진행하는 습관을 가집시다. (스스로에게 하는말)

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

int n = 0;
int arr[10001][7] = { 0, };
int result = 0;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= 6; j++)
			cin >> arr[i][j];

	for (int i = 1; i <= 6; i++) {
		bool temp[10001][7] = { 0, };
		int num = 0, next = 0;

		for (int j = 1; j <= n; j++) {
			if (j == 1) {
				num = i;
				temp[j][i] = 1;
			}
			else {
				int val = next;
				for (int u = 1; u <= 6; u++) {
					if (val == arr[j][u]) {
						temp[j][u] = 1;
						num = u;
						break;
					}
				}
			}
		

			if (num == 1) {
				next = arr[j][6];
				temp[j][6] = 1;
			}
			else if (num == 2) {
				next = arr[j][4];
				temp[j][4] = 1;
			}
			else if (num == 3) {
				next = arr[j][5];
				temp[j][5] = 1;
			}
			else if (num == 4) {
				next = arr[j][2];
				temp[j][2] = 1;
			}
			else if (num == 5) {
				next = arr[j][3];
				temp[j][3] = 1;
			}
			else if (num == 6) {
				next = arr[j][1];
				temp[j][1] = 1;
			}
			
		}



		/*
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= 6; j++)
				cout << temp[i][j] << ' ';
			cout << endl;
		}*/

		int maxed = 0;
		for (int i = 1; i <= n; i++) {
			int temp_max_num = 0;
			for (int j = 1; j <= 6; j++)
				if (temp[i][j] == 0 && temp_max_num < arr[i][j])
					temp_max_num = arr[i][j];
			maxed += temp_max_num;
		}
		result = max(result, maxed);
	}


	cout << result << endl;

	return 0;
}

문제링크:www.acmicpc.net/problem/2636

bfs를 사용한 구현문제였습니다.

단계를 나누어 구현하시면 편합니다.

• 0. 치즈가 다 녹았는지 확인
• 1. bfs를 통해서 외부 공기 표시하기
• 2. 외부 공기에 닿는 치즈를 찾아서 없애기
• 3. 최근 치즈의 개수 저장하기(0이 아닐때만)

중간중간에 테스트 코드를 통해서 올바르게 진행 되는지 확인하면 더 어려운 문제가 나오더라도 당황하지 않고 푸실 수 있을겁니다!

혹시 bfs 구현이 어렵다면 쉬운 bfs 문제들 풀어보시면 그냥 bfs 코드자체에 익숙해지셔야 합니다.

아래는 정답코드입니다.

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

int result = 0;
int result2 = 0;
int n, m;
bool arr[101][101] = { 0, };

int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

int solved(){

	//0. init
	bool jud = false;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (arr[i][j] == 1)
				jud = true;

	if (jud == false)
		return 1;

	//1. bfs 
	bool visited[101][101] = { 0, };
	queue <pair <int, int>> que;
	que.push(make_pair(1, 1));
	visited[1][1] = 1;

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny >= 1 && ny <= n && nx >= 1 && nx <= m) 
				if (arr[ny][nx] == 0 && visited[ny][nx] == 0) {
					que.push(make_pair(ny, nx));
					visited[ny][nx] = 1;
				}
			
		}

	}
	//2. 닿는 곳 찾아 없애기
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (arr[i][j] == 1) {

				for (int u = 0; u < 4; u++) {
					int ad_y = i + y_ar[u];
					int ad_x = j + x_ar[u];

					if (visited[ad_y][ad_x] == 1) {
						arr[i][j] = 0;
						break;
					}
				}
			}

	//3. 최근 갯수
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (arr[i][j] == 1)
				cnt++;
	if(cnt!=0)
		result2 = cnt;
	result++;


	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			cout << arr[i][j] << ' ';
		cout << endl;
	}*/

	return 0;

}


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

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1)
				result2++;
		}

	while (1) {
		if (solved() == 1)
			break;
	}


	cout << result << endl;
	cout << result2 << endl;
	return 0;
}

문제링크:www.acmicpc.net/problem/14719

평범한 구현문제입니다.

문제에서 준 조건은 2가지 입니다.

• 블록내부에 빈공간은 생기지 않는다.
• 바닥은 막혀있다 가정한다.

h와 w의 범위가 1 ~ 500 까지 임으로 단순 구현을 통해서 문제를 해결했습니다.  O(n^3)

500 x 500 각각의 좌표에서 빗물이 보관되는지 확인하여 구현했습니다.

쉬운문제이기 때문에 코드를 보시면 금방 이해하실겁니다.

정답코드입니다.

#include <iostream>
using namespace std;


int h = 0, w = 0;
int arr[501] = { 0, };
int result = 0;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> h >> w;
	for (int i = 1; i <= w; i++)
		cin >> arr[i];
	for (int i = 1; i <= h; i++) {
		for (int j = 2; j <= w - 1; j++) {
			if (arr[j] >= i) continue;

			bool leftt = false;
			bool rightt = false;
			//left identify
			for (int k = j - 1; k >= 1; k--) {
				if (arr[k] >= i)
				{
					leftt = true;
					break;
				}
			}
			//right identify
			for (int k = j + 1; k <= w; k++) {
				if (arr[k] >= i)
				{
					rightt = true;
					break;
				}
			}

			if (leftt == true && rightt == true)
				result++;
		}
	}

	cout << result << endl;

	return 0;
}

문제링크:https://www.acmicpc.net/problem/5624

구현문제입니다. 기존의 방식대로 구현하면 a + b + c = d 를 구하는 문제이기 때문에  O(n^3)이기 때문에 당연히 시간 초과 입니다. O(n^2)만에 해결해야 합니다. 

방법은 a + b = d - c 로 변환 하여 해결하는 것입니다.

i번째마다 이전 두개의 값 조합(a + b)으로 (d - c)를 만들 수 있는지 판별하고,

i까지의 값들의 두개의 값 조합(a + b)을 추가해주며 진행됩니다.

아래는 정답코드입니다. 구현이전 까지의 설계가 어렵고 구현자체는 쉬운 문제였습니다. 

#include <iostream>
using namespace std;

int n = 0, result = 0;
int arr[5000] = { 0 };
bool r[400000] = { 0 };

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



	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];


	for (int i = 0; i < n; i++) {

		
	
		for (int j = 0; j < i; j++) { // a + b = d - c
			if (r[arr[i] - arr[j] + 200000]) {
				result++;
				//cout << arr[i] << endl;
				break;
			}
		}
		
		for (int j = 0; j <= i; j++) { // a + b check
			r[arr[i] + arr[j] + 200000] = 1;
		}
	}
	cout << result << endl;
}

문제링크:https://www.acmicpc.net/problem/1009

단순한 구현문제였습니다.

브론즈문제가 왜 정답률이 20퍼인지 의아했는데 몇가지 함정이 있더군요

%10을 할 경우 10이 0으로 출력될 수 있는 함정과 

108^1 과 같은 값이 해당 숫자 그대로 출력 될 수 있는 함정이 있습니다.

정답코드입니다.

#include <iostream>
using namespace std;
int t = 0;
int a = 0, b = 0;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);


	cin >> t;
	while (t--) {
		long long result = 1;
		cin >> a >> b;
		result = a;
		for (int i = 0; i < b - 1; i++) {
			result *= a;
			result %= 10;
		}
		result %= 10;
		if (result == 0)
			cout << 10 << "\n";
		else
			cout << result << "\n";
	}
}