728x90

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

 

11057번: 오르막 수

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

www.acmicpc.net

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


int main() {
	int n;
	cin >> n;
	vector<vector<int>> count(1001,vector<int>(10));
	for (int i = 0; i < 10; i++) {
		count[0][i] = 1;
		count[1][i] = 10 - i;
	}
	for (int i = 2; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			for (int k = j; k < 10; k++) {
				count[i][j] = (count[i][j] + count[i - 1][k]) % 10007;
			}
		}
	}
	int total = 0;
	for (int i = 0; i < 10; i++) {
		total = (total + count[n - 1][i]) % 10007;
	}
	cout << total;
	return 0;
}
728x90

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

[백준] 14499번 주사위 굴리기  (0) 2020.02.18
[백준] 9507번 Generations of Tribbles  (0) 2020.02.17
[백준] 11727번 2×n 타일링 2  (0) 2020.02.17
[백준] 11052번 카드 구매하기  (0) 2020.02.17
[백준] 9465번 스티커  (0) 2020.02.17
728x90

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

 

11727번: 2×n 타일링 2

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

www.acmicpc.net

규칙성을 찾으면 되는 문제이다.

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int dp[1001];
	dp[1] = 1;
	dp[2] = 3;
	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
	}
	cout << dp[n];
	return 0;
}
728x90

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

[백준] 9507번 Generations of Tribbles  (0) 2020.02.17
[백준] 11057번 오르막 수  (0) 2020.02.17
[백준] 11052번 카드 구매하기  (0) 2020.02.17
[백준] 9465번 스티커  (0) 2020.02.17
[백준] 1431번 시리얼 번호  (0) 2020.02.15
728x90

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

 

11052번: 카드 구매하기

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

www.acmicpc.net

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


int main() {
	int n;
	cin >> n;
	vector<int> v(n + 1);
	v[0] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	vector<int> dp(n + 1);
	dp[1] = v[1];
	dp[0] = v[0];
	for (int i = 1; i <= n; i++) {
		int maxDp = v[i];
		for (int j = 1; j < i; j++) {
			if (dp[j] + dp[i - j] > maxDp) maxDp = dp[j] + dp[i - j];
		}
		dp[i] = maxDp;
	}
	cout << dp[n];
	return 0;
}
728x90

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

[백준] 11057번 오르막 수  (0) 2020.02.17
[백준] 11727번 2×n 타일링 2  (0) 2020.02.17
[백준] 9465번 스티커  (0) 2020.02.17
[백준] 1431번 시리얼 번호  (0) 2020.02.15
[백준] 1100번 하얀 칸  (0) 2020.02.15
728x90

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

 

9465번: 스티커

문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점

www.acmicpc.net

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


int main() {
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		int n;
		cin >> n;
		vector<vector<int>> score(2, vector<int>(n));
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < n; j++) {
				cin >> score[i][j];
			}
		}
		vector<pair<int, int>> dp(n);
		dp[0] = make_pair(score[0][0], score[1][0]);
		if (n > 1) dp[1] = make_pair(dp[0].second + score[0][1], dp[0].first + score[1][1]);
		for (int i = 2; i < n; i++) {
			dp[i].first = max(dp[i - 1].second + score[0][i], dp[i - 2].second + score[0][i]);
			dp[i].second = max(dp[i - 1].first + score[1][i], dp[i - 2].first + score[1][i]);
		}
		cout << max(dp[n - 1].first, dp[n - 1].second) << '\n';
	}
	return 0;
}

벡터 dp의 first는 윗줄을 선택했을 때, dp의 second는 아랫줄을 선택했을 때의 최댓값을 저장하도록 했다.

728x90

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

[백준] 11727번 2×n 타일링 2  (0) 2020.02.17
[백준] 11052번 카드 구매하기  (0) 2020.02.17
[백준] 1431번 시리얼 번호  (0) 2020.02.15
[백준] 1100번 하얀 칸  (0) 2020.02.15
[백준] 3474번 교수가 된 현우  (0) 2020.02.15
728x90

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

 

1431번: 시리얼 번호

첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어져 있다. 시리얼 번호는 중복되지 않는다.

www.acmicpc.net

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

bool cmp(string a, string b) {
	if (a.size() != b.size()) {
		return a.size() < b.size();
	}
	else {
		int sumOfA = 0;
		int sumOfB = 0;
		for (int i = 0; i < a.size(); i++) {
			if (a[i] < 58) {
				sumOfA += (a[i] - '0');
			}
		}
		for (int i = 0; i < b.size(); i++) {
			if (b[i] < 58) {
				sumOfB += (b[i] - '0');
			}
		}
		if (sumOfA != sumOfB) {
			return sumOfA < sumOfB; //sumOfB
		}
		else {
			return a < b;
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<string> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < n; i++)
		cout << v[i] << '\n';
	return 0;
}
728x90

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

[백준] 11052번 카드 구매하기  (0) 2020.02.17
[백준] 9465번 스티커  (0) 2020.02.17
[백준] 1100번 하얀 칸  (0) 2020.02.15
[백준] 3474번 교수가 된 현우  (0) 2020.02.15
[백준] 10816번 숫자 카드 2  (0) 2020.02.13
728x90

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

 

1100번: 하얀 칸

체스판은 8*8크기이고, 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다. 가장 왼쪽 위칸 (0,0)은 하얀색이다. 체스판의 상태가 주어졌을 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램을 작성하시오.

www.acmicpc.net

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


int main() {
	char arr[8][8];
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			cin >> arr[i][j];
		}
	}
	int count = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if ((i + j) % 2 == 0 && arr[i][j] == 'F') count++;
		}
	}
	cout << count;
	return 0;
}
728x90

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

[백준] 9465번 스티커  (0) 2020.02.17
[백준] 1431번 시리얼 번호  (0) 2020.02.15
[백준] 3474번 교수가 된 현우  (0) 2020.02.15
[백준] 10816번 숫자 카드 2  (0) 2020.02.13
[백준] 1920번 수 찾기  (0) 2020.02.13
728x90

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

 

3474번: 교수가 된 현우

문제 알고리즘의 킹갓제너럴엠퍼러마제스티충무공알고리즘마스터 현우가 교수로 취임하였다! 그러나 학생들에게 크나큰 기대를 품고 첫 수업에 들어갔던 현우는 아무도 외판원 순회 문제(Traveling Salesman Problem, TSP)를 풀지 못하는 것을 보고 낙심하였다. 그 와중에 학생 남규는 TSP를 완전탐색으로 풀려고 하였고, 현우는 그걸 보고 경악을 금치 못한다. 왜냐면 TSP를 완전탐색으로 풀려면 O(N!)의 시간이 소모되는데, 이는 경악을 금치 못

www.acmicpc.net

이렇게 제출했는데 시간초과가 났다.

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	int five[] = { 1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625, 1220703125 };
	int index = 1;
	int vectorIndex = 0;
	int now = 0;
	int previous = 0;
	for (int i = 1; i <= 1000000000; i++) {
		int increase;
		for (int j = index; j >= 0; j--) {
			if (i % five[j] == 0) {
				increase = j;
				if (j == index)
					index++;
				break;
			}
		}
		now = previous+ increase;

		if (i == v[vectorIndex]) {
			cout << now << '\n';
			vectorIndex++;
			if (vectorIndex == n) break;
		}
		previous = now;
	}
	return 0;
}

대략 반복문 수행 횟수가 10000000 넘어가면 1초 넘는데 얘는 1000000000에 이중 for문이니까 당연히 시간초과가 난다.

 

이렇게 다시 풀었다.

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		int count = 0;
		for (int j = 5; j <= num; j *= 5) {
			count += num / j;
		}
		cout << count << '\n';
	}
	return 0;
}
728x90

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

[백준] 1431번 시리얼 번호  (0) 2020.02.15
[백준] 1100번 하얀 칸  (0) 2020.02.15
[백준] 10816번 숫자 카드 2  (0) 2020.02.13
[백준] 1920번 수 찾기  (0) 2020.02.13
[백준] 2902번 KMP는 왜 KMP일까?  (0) 2020.02.12
728x90

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

 

10816번: 숫자 카드 2

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이수도 -10,00

www.acmicpc.net

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


int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> sanggeun(n);
	map<int, int> ma;
	for (int i = 0; i < n; i++) {
		cin >> sanggeun[i];
		if (ma.find(sanggeun[i]) != ma.end()) ma[sanggeun[i]]++;
		else ma[sanggeun[i]] = 1;
	}
	sort(sanggeun.begin(), sanggeun.end());
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int target;
		cin >> target;
		cout << upper_bound(sanggeun.begin(), sanggeun.end(), target) - lower_bound(sanggeun.begin(), sanggeun.end(), target) << " ";
	}
	return 0;
}
728x90

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

[백준] 1100번 하얀 칸  (0) 2020.02.15
[백준] 3474번 교수가 된 현우  (0) 2020.02.15
[백준] 1920번 수 찾기  (0) 2020.02.13
[백준] 2902번 KMP는 왜 KMP일까?  (0) 2020.02.12
[백준] 4659번 비밀번호 발음하기  (0) 2020.02.12
728x90

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

 

1920번: 수 찾기

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

www.acmicpc.net

이진탐색으로 풀어야 풀리는 문제이다.

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


int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int target;
		cin >> target;
		int start = 0; 
		int end = v.size() - 1;
		int key = -1;
		while (start <= end) {
			if (v[(start + end) / 2] == target) {
				key = (start + end) / 2;
				break;
			}
			else if (v[(start + end) / 2] > target) {
				end = (start + end) / 2 - 1;
			}
			else if (v[(start + end) / 2] < target) {
				start = (start + end) / 2 + 1;
			}
		}
		if (key == -1) cout << 0 << '\n';
		else cout << 1 << '\n';
	}
	return 0;
}

이진탐색으로 풀었더니 60ms로 성공

 

혹시나 하고 C++에 있는 find() 함수를 사용해서 풀어봤다.

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		int temp;
		cin >> temp;
		vector<int>::iterator iter;
		iter = find(arr.begin(), arr.end(), temp);
		if (iter != arr.end()) {
			cout << 1 << '\n';
		}
		else cout << 0 << '\n';
	}
	return 0;
}

무려 1796ms로 성공. 있는지 없는지 한 번만 찾아볼거면 굳이 정렬하는 시간을 들여서까지 이진탐색을 할 필요는 없는데 이 경우는 한 배열에서 어떤 숫자가 있는지 없는지 여러번 찾아볼 것이기 때문에 이진탐색이 훨씬 효율적이다. 정렬을 한 번만 해주면 그 후로 매우 빠르게 찾을 수 있다.

728x90

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

[백준] 3474번 교수가 된 현우  (0) 2020.02.15
[백준] 10816번 숫자 카드 2  (0) 2020.02.13
[백준] 2902번 KMP는 왜 KMP일까?  (0) 2020.02.12
[백준] 4659번 비밀번호 발음하기  (0) 2020.02.12
[백준] 4690번 완전 세제곱  (0) 2020.02.12
728x90

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

 

2902번: KMP는 왜 KMP일까?

문제 KMP 알고리즘이 KMP인 이유는 이를 만든 사람의 성이 Knuth, Morris, Prett이기 때문이다. 이렇게 알고리즘에는 발견한 사람의 성을 따서 이름을 붙이는 경우가 많다. 또 다른 예로, 유명한 비대칭 암호화 알고리즘 RSA는 이를 만든 사람의 이름이 Rivest, Shamir, Adleman이다. 사람들은 이렇게 사람 성이 들어간 알고리즘을 두 가지 형태로 부른다. 첫 번째는 성을 모두 쓰고, 이를 하이픈(-)으로 이어 붙인 것이다. 예

www.acmicpc.net

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


int main() {
	string s; 
	cin >> s;
	cout << s[0];
	for (int i = 1; i < s.size(); i++) {
		if (s[i] >= 65 && s[i] < 91) cout << s[i];
	}
	return 0;
}
728x90

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

[백준] 10816번 숫자 카드 2  (0) 2020.02.13
[백준] 1920번 수 찾기  (0) 2020.02.13
[백준] 4659번 비밀번호 발음하기  (0) 2020.02.12
[백준] 4690번 완전 세제곱  (0) 2020.02.12
[백준] 1592번 영식이와 친구들  (0) 2020.02.12

+ Recent posts

티스토리툴바