728x90

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

 

1526번: 가장 큰 금민수

첫째 줄에 N이 주어진다. N은 4보다 크거나 같고 1,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

#include <iostream>
using namespace std;


int main() {
	int n;
	cin >> n;
	for (int i = n; i >= 4; i--) {
		int numerator = i;
		int flag = false;
		while (numerator != 0) {
			if (numerator % 10 == 4 || numerator % 10 == 7) {
				numerator /= 10;
			}
			else {
				flag = true;
				break;
			}
		}
		if (!flag) {
			cout << i;
			return 0;
		}
	}
	return 0;
}
728x90

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

[백준] 4690번 완전 세제곱  (0) 2020.02.12
[백준] 1592번 영식이와 친구들  (0) 2020.02.12
[백준] 9237번 이장님 초대  (0) 2020.02.12
[백준] 1991번 트리 순회  (0) 2020.02.12
[백준] 6376번 e 계산  (0) 2020.02.11
728x90

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

 

9237번: 이장님 초대

문제 농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다. 상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다. 상근이는 나무를 심는 순서를 신중하게 골라 이장님을 최

www.acmicpc.net

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

bool cmp(int a, int b) {
	return a > b;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end(), cmp);
	int maxDay = 0;
	for (int i = 0; i < v.size(); i++) {
		v[i] = v[i] + i + 2;
		if (v[i] > maxDay) maxDay = v[i];
	}
	cout << maxDay;
	return 0;
}
728x90

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

[백준] 1592번 영식이와 친구들  (0) 2020.02.12
[백준] 1526번 가장 큰 금민수  (0) 2020.02.12
[백준] 1991번 트리 순회  (0) 2020.02.12
[백준] 6376번 e 계산  (0) 2020.02.11
[백준] 2979번 트럭 주차  (0) 2020.02.11
728x90

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

 

1991번: 트리 순회

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다.

www.acmicpc.net

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

map<char, pair<char, char>> m;

void preorder(char root) {
	cout << root;
	if (m[root].first != '.')
		preorder(m[root].first);
	if (m[root].second != '.')
		preorder(m[root].second);
}
void inorder(char root) {
	if (m[root].first != '.')
		inorder(m[root].first);
	cout << root;
	if (m[root].second != '.')
		inorder(m[root].second);
}
void postorder(char root) {
	if(m[root].first != '.')
		postorder(m[root].first);
	if(m[root].second != '.')
		postorder(m[root].second);
	cout << root;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		char root, left, right;
		cin >> root >> left >> right;
		m[root] = make_pair(left, right);
	}
	preorder('A');
	cout << '\n';
	inorder('A');
	cout << '\n';
	postorder('A');
	return 0;
}

자료구조 시간에 배운 것과 이런 문제를 풀 때 사용하는 자료구조에는 조금 거리가 있는 것 같다.

트리 구조체나 클래스를 직접 만들지 않아도 이렇게 풀 수 있다.

https://breakcoding.tistory.com/205

 

[C++] 포인터 없이 map으로 이진트리 구현하기, 전위, 중위, 후위순회

C++로 트리 자료구조를 구현할 때에는 보통 왼쪽 자식을 가리키는 포인터, 오른쪽 자식을 가리키는 포인터, 내 데이터 이렇게 3가지 정보를 가지고 있는 Node라는 구조체를 만들어서 구현한다. 그런데 이 방법은..

breakcoding.tistory.com

처음에는 이진트리 클래스를 직접 만들었었는데 insert하는 과정에서 위상정렬을 해야 트리에 노드를 삽입할 수 있었다.

따라서 그냥 편리하게 map을 만들었다. 다른 사람들은 어떻게 트리를 구현했는지 찾아봐야겠다.

728x90

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

[백준] 1526번 가장 큰 금민수  (0) 2020.02.12
[백준] 9237번 이장님 초대  (0) 2020.02.12
[백준] 6376번 e 계산  (0) 2020.02.11
[백준] 2979번 트럭 주차  (0) 2020.02.11
[백준] 5532번 방학 숙제  (0) 2020.02.11
728x90

C++에는 조금 더 보기 좋게 출력하게 하기 위해 스트림 조종자(manipulator)가 있다.

스트림 조종자는 <iomanip>과 <iostream> 헤더파일을 포함하면 사용할 수 있다.

사실 boolalpha, showbase, showpoint, dec, hex, oct는 <ios>에 있는 함수들인데 iostream은 ios의 자식 클래스이기 때문에 우리가 C++로 코드를 짤 때 거의 항상 포함하는 <iostream>을 포함해도 사용할 수가 있기 때문에 <iostream>이 있는데 굳이 <ios>를 따로 포함해줄 필요는 없다.

 

이 표는 manipulator와 그 기능이다.

setprecision(int n) 실수의 정밀도 설정
setw(int n) 출력되는 영역의 폭 설정
setfill(char c) 출력하고 남은 부분을 c로 채움
fixed 실수를 고정된 부동소수점 형식으로
showpoint 실수의 소수점 부분이 없어도 소수점 아래에 0을 표시
left 왼쪽 정렬
right 오른쪽 정렬
boolalpha bool 값을 1, 0이 아닌 true, false로 출력
showbase 진법기호(16진수의 경우 0x, 8진수의 경우 0)도 출력
dec 정수를 10진수로 출력
hex 정수를 16진수로 출력
oct 정수를 8진수로 출력

다음 코드를 실행하면

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

int main() {
	double a = 3.14159265358979323;
	double b = 31.4159265358979323;
	double c = 314.159265358979323;
	double d = 3141.59265358979323;
	double e = 31415.9265358979323;
	double f = 314159.265358979323;
	double g = 3141592.65358979323;
	cout << a << endl;
	cout << b << endl;
	cout << c << endl;
	cout << d << endl;
	cout << e << endl;
	cout << f << endl;
	cout << g << endl;
	return 0;
}

이런 결과가 나온다. 즉 실수는 기본적으로 소수점의 위치와는 상관 없이 6자리까지만 표기된다.

그리고 6자리가 넘어가면 3141592.65358979323처럼 3.14159e+06 이렇게 과학적 표기법으로 표기되는데 이게 싫다면 fixed를 이용하면 된다.

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

int main() {
	double a = 3.14159265358979323;
	double b = 31.4159265358979323;
	double c = 314.159265358979323;
	double d = 3141.59265358979323;
	double e = 31415.9265358979323;
	double f = 314159.265358979323;
	double g = 3141592.65358979323;
	cout << fixed << a << endl;
	cout << b << endl;
	cout << c << endl;
	cout << d << endl;
	cout << e << endl;
	cout << f << endl;
	cout << g << endl;
	return 0;
}

이렇게 fixed만 한 번 써주면

e를 사용한 과학적 표기법이 아니라 우리가 일상에서 쓰는 소수점 표현으로 출력된다. 그리고 fixed를 사용해주니 전체 자리수가 6자리까지가 아니라 소수점 아래 6자리까지 출력된다. fixed는 기본이 소수점 아래 6자리이다.

 

그런데 실제로 내가 저장한 숫자보다 출력된 숫자가 소수점 아래가 잘려서 정확도가 너무 떨어진다면 setprecision 함수를 사용해서 몇 자리를 표기할지 정해주면 된다.

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

int main() {
	double a = 3.14159265358979323;
	double b = 31.4159265358979323;
	double c = 314.159265358979323;
	double d = 3141.59265358979323;
	double e = 31415.9265358979323;
	double f = 314159.265358979323;
	double g = 3141592.65358979323;
	cout << setprecision(18) << a << endl;
	cout << b << endl;
	cout << c << endl;
	cout << d << endl;
	cout << e << endl;
	cout << f << endl;
	cout << g << endl;
	return 0;
}

 

이렇게 setprecision() 함수로 정해주면 18자리가 모두  나타난 것을 볼 수 있다. setprecision() 함수는 한 번만 써주면 setprecision() 함수로 다시 바꾸기 전까지는 계속 유효하다.

하지만 소수점 아래쪽으로 갈수록 정확도가 떨어지는 것을 볼 수 있다.

 

그럼 setprecision() 함수를 fixed와 같이 써보자.

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

int main() {
	double a = 3.14159265358979323;
	double b = 31.4159265358979323;
	double c = 314.159265358979323;
	double d = 3141.59265358979323;
	double e = 31415.9265358979323;
	double f = 314159.265358979323;
	double g = 3141592.65358979323;
	cout << fixed << setprecision(18) << a << endl;
	cout << b << endl;
	cout << c << endl;
	cout << d << endl;
	cout << e << endl;
	cout << f << endl;
	cout << g << endl;
	return 0;
}

내가 저장했던 숫자인 314159265358979323까지는 모두 아주 정확하게 출력된 것을 볼 수 있다. 그 아래 자리는 아무 숫자나 출력되었다.

fixed를 사용하고 setprecision() 함수를 사용하면 소수점 아래 몇 번째 자리까지 나타낼 것인지를 정해주는 것이다. 그냥 setprecision() 함수를 사용했을 때에는 소수점과 상관없이 숫자 몇 개를 나타낼지를 정해주는 거였다. 둘의 차이를 기억하자.

그리고 setprecision()을사용할 때에는 원래 숫자의 자릿수보다 더 큰 숫자를 넣으면 저렇게 이상한 숫자가 출력될 수도 있다. 실수는 정수와 달리 저장할 때 정확도가 떨어진다. 모든 정수는 모두 정확한 이진수로 바꿀 수 있지만 실수는 소수점 아래를 정확한 이진수로 표현하기 힘든 경우가 있기 때문이다.

 

하지만 위의 예처럼 소수점 아래가 매우 많은 숫자 말고 이 정도 숫자는 정확하게 출력한다.

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

int main() {
	double a = 3.14;
	double b = 3.1415;
	double c = 3.1415926;
	cout << setprecision(5) << a << endl;
	cout << b << endl;
	cout << c << endl;
	return 0;
}

그리고 setprecision() 함수를 사용해서 잘린 부분은 그 뒤의 수에서 반올림해서 출력된다.

 

그런데 만약 모든 수의 소수점 아래 자리가 동일하고 3.14와 같 소수점 아래 숫자가 짧은 것들은 0으로 채우고 싶다면? 그러면 showpoint를 사용하면 된다.

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

int main() {
	double i = 3.0;
	double a = 3.14;
	double b = 3.1415;
	double c = 3.1415926;
	cout << i << endl;
	cout << showpoint << setprecision(7) << i << endl;
	cout << a << endl;
	cout << b << endl;
	cout << c << endl;
	return 0;
}

showpoint를 사용하면 이렇게 3.0과 같은 소수점 아래가 없는 숫자도 내가 정해준 만큼 0을 출력할 수 있다.

 

그러면 이제 다른 조종자를 배워보자.

#include <iostream>
using namespace std;

int main() {
	int arr[10][10];
	int num = 1;
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			arr[i][j] = num;
			num++;
		}
	}
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

이 코드를 실행하면

이렇게 줄이 안 맞아서 보기 안 좋게 출력된다.

이 때 setw()를 사용하면 줄 맞춰서 예쁘게 출력할 수 있다.

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

int main() {
	int arr[10][10];
	int num = 1;
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			arr[i][j] = num;
			num++;
		}
	}
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			cout << setw(3) << arr[i][j];
		}
		cout << endl;
	}
	return 0;
}

setw()를 이용했더니 이렇게 줄맞춰서 예쁘게 출력되었다.

setw(n)은 n칸을 확보해놓는다는 것이다. 확보해놓고 그 안에서 내가 출력하고 싶은 것을 출력하는 것이다. 확보해놓은 칸보다 내가 출력하고 싶은 것이 더 많은 칸을 차지한다면 자동으로 칸이 증가되기 때문에 잘릴 걱정은 하지 않아도 된다.

setw()를 쓸 때 주의해야 할 것은 setw()를 쓴 직후의 출력에만 유효하다는 것이다.

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

int main() {
	cout << setw(7) << "orange" << "cat" << "peach" << endl;
	return 0;
}

이렇게 setw(7)을 orange 직전에 써주면

이렇게 orange에만 유효하다.

따라서 이렇게 출력하기 전에 매번 써줘야 한다.

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

int main() {
	cout << setw(7) << "orange" << setw(7) << "cat" << setw(7) << "peach" << endl;
	return 0;
}

showpoint, fixed, setprecision과는 달리 딱 한 번만 유효하다는 거 기억하자.

 

그런데 setw()를 쓰면 자동으로 오른쪽으로 정렬이 되었는데 왼쪽으로 정렬하고 싶다면?

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

int main() {
	int arr[10][10];
	int num = 1;
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			arr[i][j] = num;
			num++;
		}
	}
	cout << left;
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			cout << setw(3) << arr[i][j];
		}
		cout << endl;
	}
	return 0;
}

이렇게 left를 써주면 왼쪽으로 정렬되어 출력된다.

오른쪽으로 정렬하고 싶다면 left 대신 right를 써주면 된다. (right가 기본값이다.)

left도 setprecision, showpoint, fixed처럼 한 번만 써주면 right로 바꾸기 전까지는 유효하다.

(딱 한 번만 유효한 것은 setw()이다.)

 

그런데 setw()로 확보하느라 생기는 공백을 다른 문자로 채우고 싶다면?

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

int main() {
	int arr[10][10];
	int num = 1;
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			arr[i][j] = num;
			num++;
		}
	}
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			cout << setfill('#') << setw(3) << arr[i][j];
		}
		cout << endl;
	}
	return 0;
}

이렇게 setw 전에 setfill(채우고 싶은 문자)를 써주면 된다.

주의할 것은 문자열은 안 되고 char형 문자를 써줘야 한다.

 

표에 있지만 설명하지 않은 것들은 그냥 보면 어떻게 쓰면 되는지 간단하기 때문에 누구나 쉽게 쓸 수 있다.

이 외에도 더 많은 조종자를 알고 싶다면

http://www.cplusplus.com/reference/ios/

 

- C++ Reference

header Input-Output base classes Header providing base classes and types for the IOStream hierarchy of classes: Types Class templates basic_iosBase class for streams (type-dependent components) (class template )fposStream position class template (class tem

www.cplusplus.com

http://www.cplusplus.com/reference/iomanip/

 

- C++ Reference

 

www.cplusplus.com

여기에 들어가서 보는 것을 추천한다.

728x90
728x90

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

 

6376번: e 계산

문제 e는 \[e=\sum_{i=0}^{n} {\frac{1}{i!}}\] 이다. 여기서 n은 무한대이다. 매우 작은 n에 대해서, e의 근사값을 구해보자. 출력 아래 결과와 같은 형식으로 e의 근사값을 n = 0부터 9까지 출력한다.  예제 입력 1 복사 예제 출력 1 복사 n e - ----------- 0 1 1 2 2 2.5 3 2.666666667 4 2.708333333...

www.acmicpc.net

문제 자체는 어렵지 않았는데 출력 형식 조정하느라 애를 먹었다.

처음에는 for문을 0부터 9까지 돌리면서 cout << n << setprecision(10) << sum <<'\n'; 했는데 틀려서

for문을 0부터 9까지 돌리면서 cout << n << " " << fixed << setprecision(9) << sum << '\n'; 했는데 또 틀렸다.

 

결국은 for를 둘로 나눠서 출력했더니 맞았다.

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

int main() {
	cout << "n e" << '\n';
	cout << "- -----------" << '\n';
	for (int n = 0; n <= 2; n++) { //n
		double sum = 0;
		for (int i = 0; i <= n; i++) {
			int denominator = 1;
			for (int j = i; j > 0; j--) {
				denominator *= j;
			}
			sum += (1 / (double)denominator);
		}
		cout << n << " " << sum << '\n';
	}
	for (int n = 3; n <= 9; n++) { //n
		double sum = 0;
		for (int i = 0; i <= n; i++) {
			int denominator = 1;
			for (int j = i; j > 0; j--) {
				denominator *= j;
			}
			sum += (1 / (double)denominator);
		}
		cout << n << " " << fixed << setprecision(9) << sum << '\n';
	}
	return 0;
}
728x90
728x90

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

 

2979번: 트럭 주차

문제 상근이는 트럭을 총 세 대 가지고 있다. 오늘은 트럭을 주차하는데 비용이 얼마나 필요한지 알아보려고 한다. 상근이가 이용하는 주차장은 주차하는 트럭의 수에 따라서 주차 요금을 할인해 준다. 트럭을 한 대 주차할 때는 1분에 한 대당 A원을 내야 한다. 두 대를 주차할 때는 1분에 한 대당 B원, 세 대를 주차할 때는 1분에 한 대당 C원을 내야 한다. A, B, C가 주어지고, 상근이의 트럭이 주차장에 주차된 시간이 주어졌을 때, 주차 요금으로 얼마

www.acmicpc.net

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


int main() {
	int fee[3];
	for (int i = 0; i < 3; i++) {
		cin >> fee[i];
	}
	int arriveTime[3];
	int leaveTime[3];
	vector<pair<int, int>> time;
	for (int i = 0; i < 3; i++) {
		cin >> arriveTime[i];
		cin >> leaveTime[i];
		time.push_back(make_pair(arriveTime[i], 1));
		time.push_back(make_pair(leaveTime[i], -1));
	}
	sort(time.begin(), time.end());
	int count = 1;
	int totalFee = 0;
	int previousTime = time[0].first;
	for (int i = 1; i < 6; i++) {
		int feePerHour = fee[count - 1];
		int now = time[i].first;
		totalFee += ((now - previousTime) * feePerHour * count);
		count += time[i].second;
		previousTime = time[i].first;
 	}
	
	cout << totalFee;
	return 0;
}

어제도 그래놓고는.. 오늘도 다짐한다. 문제를 똑바로 읽자.

트럭 1대면 A원, 2대면 B원, 3대면 C원인 줄 알았는데 한 대당 A원, B원, C원이었다.

728x90
728x90

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

 

5532번: 방학 숙제

문제 상근이는 초등학교에 다닐 때, 방학 숙제를 남들보다 먼저 미리 하고 남은 기간을 놀았다. 방학 숙제는 수학과 국어 문제 풀기이다. 방학은 총 L일이다. 수학은 총 B페이지, 국어는 총 A페이지를 풀어야 한다. 상근이는 하루에 국어를 최대 C페이지, 수학을 최대 D페이지 풀 수 있다. 상근이가 겨울 방학동안 숙제를 하지 않고 놀 수 있는 최대 날의 수를 구하는 프로그램을 작성하시오. 입력 한 줄에 하나씩 총 다섯 줄에 걸쳐 L, A, B, C, D가

www.acmicpc.net

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


int main() {
	int vacationDays, koreanTotal, mathTotal, koreanMaxPage, mathMaxPage;
	cin >> vacationDays >> koreanTotal >> mathTotal >> koreanMaxPage >> mathMaxPage;
	int days = 1;
	while (true) {
		koreanTotal -= koreanMaxPage;
		mathTotal -= mathMaxPage;
		if (koreanTotal <= 0 && mathTotal <= 0) break;
		days++;
	}
	cout << vacationDays - days;
	return 0;
}
728x90

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

[백준] 6376번 e 계산  (0) 2020.02.11
[백준] 2979번 트럭 주차  (0) 2020.02.11
[백준] 2661번 좋은 수열 (시간초과로 미해결)  (0) 2020.02.11
[백준] 1759번 암호 만들기  (0) 2020.02.11
[백준] 4641번 Doubles  (0) 2020.02.11
728x90

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

 

2661번: 좋은수열

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

www.acmicpc.net

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

int n;
bool foundAnswer = false;

void select(vector<int> result, int num) {
	if (foundAnswer) return;
	if (num == n) {
		string s = "";
		for (int i = 0; i < n; i++) {
			s += to_string(result[i]);
		}
		for (int i = 0; i < n; i++) { //어디서부터 시작하는지
			for (int j = 1; j < n - i; j++) { //몇개짜리 수열인지
				if (s.substr(i, j) == s.substr(i + j, j)) {
					return;
				}
			}
		}

		foundAnswer = true;
		for (int i = 0; i < n; i++) {
			cout << result[i];
		}
		return;
	}
	for (int i = 1; i <= 3; i++) {
		result[num] = i;
		select(result, num + 1);
	}
}

int main() {
	cin >> n;
	vector<int> result(n);
	select(result, 0);
	return 0;
}

시간초과

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

int n;
bool foundAnswer = false;

void select(string result, int num) {
	if (foundAnswer) return;
	if (num == n) {
		for (int i = 0; i < n; i++) { //어디서부터 시작하는지
			for (int j = 1; j < n - i; j++) { //몇개짜리 수열인지
				if (result.substr(i, j) == result.substr(i + j, j)) {
					return;
				}
			}
		}

		foundAnswer = true;
		cout << result;
		return;
	}
	for (int i = 0; i < 3; i++) {
		result[num] = '1' + i;
		select(result, num + 1);
	}
}

int main() {
	cin >> n;
	string result("");
	for (int i = 0; i < n; i++)
		result.append("1");
	select(result, 0);
	return 0;
}

애초에 string으로 해보았다. 이것도 시간초과

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

int n;
bool foundAnswer = false;

void select(string result, int num) {
	if (foundAnswer) return;
	if (num == n) {
		for (int i = 0; i < n; i++) { //어디서부터 시작하는지
			for (int j = 2; j < n - i; j++) { //몇개짜리 수열인지
				if (result.substr(i, j) == result.substr(i + j, j)) {
					return;
				}
			}
		}

		foundAnswer = true;
		cout << result;
		return;
	}
	for (int i = 0; i < 3; i++) {
		if (num == 0) {
			result[num] = '1' + i;
			select(result, num + 1);
		}
		else {
			if (result[num - 1] == '1' + i) continue;
			result[num] = '1' + i;
			select(result, num + 1);
		}
	}
}

int main() {
	cin >> n;
	string result("");
	for (int i = 0; i < n; i++)
		result.append("1");
	select(result, 0);
	return 0;
}

재귀호출 전에 인접한 것이 같으면 재귀호출을 안 하도록 했는데 이것도 시간초과

728x90

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

[백준] 2979번 트럭 주차  (0) 2020.02.11
[백준] 5532번 방학 숙제  (0) 2020.02.11
[백준] 1759번 암호 만들기  (0) 2020.02.11
[백준] 4641번 Doubles  (0) 2020.02.11
[백준] 6321번 IBM 빼기 1  (0) 2020.02.10
728x90

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

 

1759번: 암호 만들기

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

www.acmicpc.net

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

int r, n;
vector<char> v;

void select(vector<bool> visited, vector<char> result, int num) {
	if (num == r) {
		int vowelCount = 0;
		int consonantCount = 0;	
		for (int i = 0; i < r; i++) {
			if (result[i] == 'a' || result[i] == 'e' || result[i] == 'i' || result[i] == 'o' || result[i] == 'u') 
				vowelCount++;
			else 
				consonantCount++;
		}
		if (!(vowelCount >= 1 && consonantCount >= 2)) {
			return;
		}
		for (int i = 0; i < r; i++) {
			cout << result[i];
		}
		cout << '\n';
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			if (num == 0) {
				visited[i] = true;
				result[num] = v[i];
				select(visited, result, num + 1);
				visited[i] = false;
			}
			else {
				if (result[num - 1] < v[i]) {
					visited[i] = true;
					result[num] = v[i];
					select(visited, result, num + 1);
					visited[i] = false;
				}
			}
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> r >> n;
	for (int i = 0; i < n; i++) {
		char temp;
		cin >> temp;
		v.push_back(temp);
	}
	sort(v.begin(), v.end());
	vector<char> result(r);
	vector<bool> visited(n);
	select(visited, result, 0);
	return 0;
}
728x90
728x90

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

 

4641번: Doubles

문제 2~15개의 서로 다른 자연수로 이루어진 리스트가 있을 때, 이들 중 리스트 안에 자신의 정확히 2배인 수가 있는 수의 개수를 구하여라. 예를 들어, 리스트가 "1 4 3 2 9 7 18 22"라면 2가 1의 2배, 4가 2의 2배, 18이 9의 2배이므로 답은 3이다. 입력 입력은 여러 개의 테스트 케이스로 주어져 있으며, 입력의 끝에는 -1이 하나 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 2~15개의 서로 다른 자연수가 주어진다.

www.acmicpc.net

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

int main() {
	while (true) {
		int first;
		cin >> first;
		if (first == -1) break;
		vector<int> v;
		v.push_back(first);
		while (true) {
			int n;
			cin >> n;
			if (n == 0) break;
			v.push_back(n);

		}
		int count = 0;
		for (int i = 0; i < v.size(); i++) {
			for (int j = 0; j < v.size(); j++) {
				if (v[j] == v[i] * 2) count++;
			}
		}
		cout << count << '\n';
	}
	return 0;
}
728x90

+ Recent posts