'분류 전체보기' 카테고리의 글 목록 (14 Page)

분류 전체보기

728x90

[백준] 2206번 벽 부수고 이동하기 2020.03.03
[백준] 11816번 8진수, 10진수, 16진수 2020.03.03
[백준] 2752번 세수정렬 2020.03.03
[백준] 3896번 소수 사이 수열 2020.03.03
[백준] 9020번 골드바흐의 추측 2020.03.03
[백준] 5337번 웰컴 2020.03.01
[백준] 1011번 Fly me to the Alpha Centauri 2020.03.01
[백준] 9252번 LCS 2 2020.03.01
[백준] 11055번 가장 큰 증가 부분 수열 2020.02.29
[백준] 15969번 행복 2020.02.29

이전 1 ···11 12 13 14 15 16 17 ···37 다음

[백준] 2206번 벽 부수고 이동하기

2020. 3. 3. 22:13

728x90

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

2206번: 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동

www.acmicpc.net

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


int main() {
	int n, m;
	cin >> n >> m;
	vector<string> map;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		map.push_back(s);
	}

	queue<tuple<int, int, int, int>> q;
	q.push(make_tuple(0, 0, 0, 1)); //행, 열, 벽 부쉈는지 아닌지, 현재까지 몇 칸 거쳐왔는지
	vector<vector<vector<bool>>> visited(2, vector<vector<bool>>(n));
	for (int i = 0; i < 2; i++) {
		for(int j = 0; j < n; j++)
			visited[i][j] = vector<bool>(m);
	}
	vector<int> distance;
	while (!q.empty()) {
		tuple<int, int, int, int> cur = q.front();
		q.pop();
		if (!visited[get<2>(cur)][get<0>(cur)][get<1>(cur)]) {
			if(map[get<0>(cur)][get<1>(cur)] == '0')
				visited[get<2>(cur)][get<0>(cur)][get<1>(cur)] = true;
			if (get<0>(cur) == n - 1 && get<1>(cur) == m - 1) {
				distance.push_back(get<3>(cur));
			}
			else {
				if (get<0>(cur) - 1 >= 0 && map[get<0>(cur) - 1][get<1>(cur)] == '0' && !visited[get<2>(cur)][get<0>(cur) - 1][get<1>(cur)]) {
					q.push(make_tuple(get<0>(cur) - 1, get<1>(cur), get<2>(cur), get<3>(cur) + 1));
				}
				if (get<0>(cur) + 1 < n && map[get<0>(cur) + 1][get<1>(cur)] == '0' && !visited[get<2>(cur)][get<0>(cur) + 1][get<1>(cur)]) {
					q.push(make_tuple(get<0>(cur) + 1, get<1>(cur), get<2>(cur), get<3>(cur) + 1));
				}
				if (get<1>(cur) - 1 >= 0 && map[get<0>(cur)][get<1>(cur) - 1] == '0' && !visited[get<2>(cur)][get<0>(cur)][get<1>(cur) - 1]) {
					q.push(make_tuple(get<0>(cur), get<1>(cur) - 1, get<2>(cur), get<3>(cur) + 1));
				}
				if (get<1>(cur) + 1 < m && map[get<0>(cur)][get<1>(cur) + 1] == '0' && !visited[get<2>(cur)][get<0>(cur)][get<1>(cur) + 1]) {
					q.push(make_tuple(get<0>(cur), get<1>(cur) + 1, get<2>(cur), get<3>(cur) + 1));
				}


				if (get<0>(cur) - 1 >= 0 && map[get<0>(cur) - 1][get<1>(cur)] == '1' && get<2>(cur) == 0 && !visited[get<2>(cur)][get<0>(cur) - 1][get<1>(cur)]) {
					q.push(make_tuple(get<0>(cur) - 1, get<1>(cur), get<2>(cur) + 1, get<3>(cur) + 1));
				}
				if (get<0>(cur) + 1 < n && map[get<0>(cur) + 1][get<1>(cur)] == '1' && get<2>(cur) == 0 && !visited[get<2>(cur)][get<0>(cur) + 1][get<1>(cur)]) {
					q.push(make_tuple(get<0>(cur) + 1, get<1>(cur), get<2>(cur) + 1, get<3>(cur) + 1));
				}
				if (get<1>(cur) - 1 >= 0 && map[get<0>(cur)][get<1>(cur) - 1] == '1' && get<2>(cur) == 0 && !visited[get<2>(cur)][get<0>(cur)][get<1>(cur) - 1]) {
					q.push(make_tuple(get<0>(cur), get<1>(cur) - 1, get<2>(cur) + 1, get<3>(cur) + 1));
				}
				if (get<1>(cur) + 1 < m && map[get<0>(cur)][get<1>(cur) + 1] == '1' && get<2>(cur) == 0 && !visited[get<2>(cur)][get<0>(cur)][get<1>(cur) + 1]) {
					q.push(make_tuple(get<0>(cur), get<1>(cur) + 1, get<2>(cur) + 1, get<3>(cur) + 1));
				}
			}
		}
	}
	if (distance.empty()) cout << -1;
	else {
		int minDist = 1000001;
		for (int i = 0; i < distance.size(); i++) {
			if (distance[i] < minDist)
				minDist = distance[i];
		}
		cout << minDist;
	}
	return 0;
}

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 1002번 터렛 (0)	2020.03.07
[백준] 5543번 상근날드 (0)	2020.03.07
[백준] 11816번 8진수, 10진수, 16진수 (0)	2020.03.03
[백준] 2752번 세수정렬 (0)	2020.03.03
[백준] 3896번 소수 사이 수열 (0)	2020.03.03

[백준] 11816번 8진수, 10진수, 16진수

2020. 3. 3. 01:32

728x90

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

11816번: 8진수, 10진수, 16진수

첫째 줄에 X가 주어진다. X는 10진수로 바꿨을 때, 1,000,000보다 작거나 같은 자연수이다. 16진수인 경우 알파벳은 소문자로만 이루어져 있다.

www.acmicpc.net

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


int main() {
	string s;
	cin >> s;
	if (s[0] >= '1' && s[0] <= '9') {
		cout << s;
	}
	else if (s[1] == 'x') {
		s.erase(0, 2);
		int total = 0;
		for (int i = s.size() - 1; i >= 0; i--) {
			if(s[i] <= '9')
				total += ((s[i] - '0') * pow(16, s.size() - 1 - i));
			else 
				total += ((s[i] - 'a' + 10) * pow(16, s.size() - 1 - i));
		}
		cout << total;
	}
	else {
		s.erase(0, 1);
		int total = 0;
		for (int i = s.size() - 1; i >= 0; i--) {
			total += ((s[i] - '0') * pow(8, s.size() - 1 - i));
		}
		cout << total;
	}
	return 0;
}

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 5543번 상근날드 (0)	2020.03.07
[백준] 2206번 벽 부수고 이동하기 (0)	2020.03.03
[백준] 2752번 세수정렬 (0)	2020.03.03
[백준] 3896번 소수 사이 수열 (0)	2020.03.03
[백준] 9020번 골드바흐의 추측 (0)	2020.03.03

[백준] 2752번 세수정렬

2020. 3. 3. 01:10

728x90

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

2752번: 세수정렬

숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다.

www.acmicpc.net

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


int main() {
	int arr[3];
	for (int i = 0; i < 3; i++)
		cin >> arr[i];
	sort(arr, arr + 3);
	for (int i = 0; i < 3; i++)
		cout << arr[i] << " ";
	return 0;
}

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 2206번 벽 부수고 이동하기 (0)	2020.03.03
[백준] 11816번 8진수, 10진수, 16진수 (0)	2020.03.03
[백준] 3896번 소수 사이 수열 (0)	2020.03.03
[백준] 9020번 골드바흐의 추측 (0)	2020.03.03
[백준] 5337번 웰컴 (0)	2020.03.01

[백준] 3896번 소수 사이 수열

2020. 3. 3. 01:03

728x90

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

3896번: 소수 사이 수열

문제 연속한 소수 p와 p+n이 있을 때, 그 사이에 있는 n-1개의 합성수(소수나 1이 아닌 양의 정수)는 길이가 n인 소수 사이 수열라고 부른다. 양의 정수 k가 주어졌을 때, k를 포함하는 소수 사이 수열의 길이를 구하는 프로그램을 작성하시오. k를 포함하는 소수 사이 수열이 없을 때는 길이가 0이다. 예를 들어, 소수 23과 29의 소수 사이 수열은 {24, 25, 26, 27, 28}이고, 길이는 6이다. 입력 첫째 줄에 테스트 케이스의 개수 T

www.acmicpc.net

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

bool arr[1299710] = { false };
int where[1299710] = { 0 };

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	vector<int> primeNumber;
	arr[1] = true;
	for (int i = 2; i <= 1299709; i++) {
		if (!arr[i]) {
			primeNumber.push_back(i);
			where[i] = primeNumber.size() - 1;
			for (int j = 2; ; j++) {
				if (j * i > 1299709) break;
				arr[i * j] = true;
			}
		}
	}
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		if (arr[num]) {
			for (int j = num - 1; ; j--) {
				if (!arr[j]) {
					cout << primeNumber[where[j] + 1] - primeNumber[where[j]] << '\n';
					break;
				}
			}
		}
		else cout << 0 << '\n';
	}
	return 0;
}

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 11816번 8진수, 10진수, 16진수 (0)	2020.03.03
[백준] 2752번 세수정렬 (0)	2020.03.03
[백준] 9020번 골드바흐의 추측 (0)	2020.03.03
[백준] 5337번 웰컴 (0)	2020.03.01
[백준] 1011번 Fly me to the Alpha Centauri (0)	2020.03.01

[백준] 9020번 골드바흐의 추측

2020. 3. 3. 00:30

728x90

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

9020번: 골드바흐의 추측

문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.

www.acmicpc.net

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


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	bool arr[10001] = { false };
	vector<int> primeNumber;
	arr[1] = true;
	for (int i = 2; i <= 10000; i++) {
		if (!arr[i]) {
			primeNumber.push_back(i);
			for (int j = 2; ; j++) {
				if (j * i > 10000) break;
				arr[i * j] = true;
			}
		}
	}
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		int a, b;
		for (int j = 0; j < primeNumber.size(); j++) {
			if (primeNumber[j] > num / 2) break;
			if (!arr[num - primeNumber[j]]) {
				a = primeNumber[j];
				b = num - primeNumber[j];
			}
		}
		cout << a << " " << b << '\n';
	}
	return 0;
}

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 2752번 세수정렬 (0)	2020.03.03
[백준] 3896번 소수 사이 수열 (0)	2020.03.03
[백준] 5337번 웰컴 (0)	2020.03.01
[백준] 1011번 Fly me to the Alpha Centauri (0)	2020.03.01
[백준] 9252번 LCS 2 (0)	2020.03.01

[백준] 5337번 웰컴

2020. 3. 1. 23:43

728x90

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

5337번: 웰컴

문제 Welcome을 예제 출력처럼 출력하는 프로그램을 작성하시오. 출력 Welcome을 아래 예제 출력처럼 출력한다. 예제 입력 1 복사 예제 출력 1 복사 . . . | | _ | _. _ ._ _ _ |/\|(/.|(_.(_)[ | )(/....

www.acmicpc.net

#include <iostream>
using namespace std;


int main() {
	cout << ".  .   ." << endl;
	cout << "|  | _ | _. _ ._ _  _" << endl;
	cout << "|/\\\|(/.|(_.(_)[ | )(/.";
	return 0;
}

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 3896번 소수 사이 수열 (0)	2020.03.03
[백준] 9020번 골드바흐의 추측 (0)	2020.03.03
[백준] 1011번 Fly me to the Alpha Centauri (0)	2020.03.01
[백준] 9252번 LCS 2 (0)	2020.03.01
[백준] 11055번 가장 큰 증가 부분 수열 (0)	2020.02.29

[백준] 1011번 Fly me to the Alpha Centauri

2020. 3. 1. 23:35

728x90

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

1011번: Fly me to the Alpha Centauri

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을

www.acmicpc.net

출발지 x와 도착지 y 사이의 거리를 구하고 그 차이가

거리		이동횟수
1	1의 제곱	1 (= 1 * 2 - 1)	1개 연속 1
2		2	1개 연속 2
3		3	2개 연속 3
4	2의 제곱	3 (= 2 * 2 - 1)	2개 연속 3
5		4	2개 연속 4
6		4	2개 연속 4
7		5	3개 연속 5
8		5
9	3의 제곱	5 (= 3 * 2 - 1)
10		6	3개 연속 6
11		6
12		6
13		7	4개 연속 7
14		7
15		7
16	4의 제곱	7 (= 4 * 2 - 1)
17		8	4개 연속 8
18		8
19		8
20		8
21		9	5개 연속 9
22		9
23		9
24		9
25	5의 제곱	9 (= 5 * 2 - 1)
26		10	5개 연속 10
27		10
28		10
29		10
30		10

이 규칙만 이용하면 된다

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


int main() {
	long long testCase;
	cin >> testCase;
	for (long long t = 0; t < testCase; t++) {
		long long x, y;
		cin >> x >> y;
		long long distance = y - x;
		if (sqrt(distance) == ceil(sqrt(distance))) cout << sqrt(distance) * 2 - 1 << '\n';
		else if (pow(floor(sqrt(distance)), 2) + floor(sqrt(distance)) >= distance) {
			cout << floor(sqrt(distance)) * 2 << '\n';
		}
		else cout << floor(sqrt(distance)) * 2 + 1 << '\n';
	}
	return 0;
}

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 9020번 골드바흐의 추측 (0)	2020.03.03
[백준] 5337번 웰컴 (0)	2020.03.01
[백준] 9252번 LCS 2 (0)	2020.03.01
[백준] 11055번 가장 큰 증가 부분 수열 (0)	2020.02.29
[백준] 15969번 행복 (0)	2020.02.29

[백준] 9252번 LCS 2

2020. 3. 1. 00:59

728x90

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

9252번: LCS 2

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

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


int main() {
	string s1, s2;
	cin >> s1 >> s2;
	vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1));
	for (int i = 0; i <= s1.size(); i++) {
		dp[i][0] = 0;
	}
	for (int i = 0; i <= s2.size(); i++) {
		dp[0][i] = 0;
	}

	for (int i = 1; i <= s1.size(); i++) {
		for (int j = 1; j <= s2.size(); j++) {
			if (s1[i - 1] == s2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	/*cout << "    ";
	for (int i = 0; i < s2.size(); i++) {
		cout << s2[i] << " ";
	}
	cout << endl;
	for (int i = 0; i <= s1.size(); i++) {
		if (i != 0) {
			cout << s1[i - 1] << " ";
		}
		else cout << "  ";
		for (int j = 0; j <= s2.size(); j++) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}*/

	cout << dp[s1.size()][s2.size()] << endl;
	string result = "";
	int nowRow = s1.size();
	int nowCol = s2.size();
	while (true) {
		if (nowRow == 0 || nowCol == 0) break;
		if (dp[nowRow][nowCol] != dp[nowRow - 1][nowCol] && dp[nowRow][nowCol] != dp[nowRow][nowCol - 1]) {
			result += s1[nowRow - 1];
			nowRow--;
			nowCol--;
		}
		else if (dp[nowRow][nowCol] == dp[nowRow - 1][nowCol]) {
			nowRow--;
		}
		else nowCol--;
	}
	for (int i = result.size() - 1; i >= 0; i--)
		cout << result[i];
	return 0;
}

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 5337번 웰컴 (0)	2020.03.01
[백준] 1011번 Fly me to the Alpha Centauri (0)	2020.03.01
[백준] 11055번 가장 큰 증가 부분 수열 (0)	2020.02.29
[백준] 15969번 행복 (0)	2020.02.29
[백준] 2475번 검증수 (0)	2020.02.29

[백준] 11055번 가장 큰 증가 부분 수열

2020. 2. 29. 16:43

728x90

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

11055번: 가장 큰 증가 부분 수열

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

www.acmicpc.net

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


int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i].first;
		v[i].second = v[i].first;
	}
	int realMax = v[0].first;
	for (int i = 1; i < n; i++) {
		int maxSum = 0;
		for (int j = 0; j < i; j++) {
			if (v[j].first < v[i].first && v[j].second > maxSum) maxSum = v[j].second;
		}
		v[i].second = v[i].first + maxSum;
		if (v[i].second > realMax) realMax = v[i].second;
	}
	cout << realMax;
	return 0;
}

처음엔 realMax = 1;로 초기화를 시켰었는데 100%에서 틀렸다. 이제 초기화를 시킬 때 0이나 1이 아니라 첫 번째 원소로 초기화시켜야겠다. 잊지 말자

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 1011번 Fly me to the Alpha Centauri (0)	2020.03.01
[백준] 9252번 LCS 2 (0)	2020.03.01
[백준] 15969번 행복 (0)	2020.02.29
[백준] 2475번 검증수 (0)	2020.02.29
[백준] 15657번 N과 M (8) (0)	2020.02.29

[백준] 15969번 행복

2020. 2. 29. 03:41

728x90

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

15969번: 행복

모든 서브태스크에서 2 ≤ N ≤ 1,000이고 입력되는 학생들의 점수는 0 이상 1,000 이하의 정수이다.

www.acmicpc.net

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


int main() {
	int n;
	cin >> n;
	vector<int> v(n);
	int minN = 1000;
	int maxN = 0;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		if (v[i] < minN) minN = v[i];
		if (v[i] > maxN) maxN = v[i];
	}
	cout << maxN - minN;
	return 0;
}

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 9252번 LCS 2 (0)	2020.03.01
[백준] 11055번 가장 큰 증가 부분 수열 (0)	2020.02.29
[백준] 2475번 검증수 (0)	2020.02.29
[백준] 15657번 N과 M (8) (0)	2020.02.29
[백준] 1934번 최소공배수 (0)	2020.02.29

Feel Coding