대엉코딩

www.acmicpc.net/problem/1793

1. 풀이방법

- 점화식을 찾는 것은 어렵지 않습니다.

- 그림 몇개 그려보고 생각 해보면 dp[i]=dp[i-1]+dp[i-2]*2 입니다.

- 하지만 더 큰 문제는 c++에서 제공해주는 정수 자료형으로는 이 문제의 출력을 담아 낼 수 없습니다.

- 그래서 저 같은 이차원으로 벡터를 이용해서 벡터의 한 원소당 한 자리의 숫자를 담아서 표현하였고,

- 점화식을 보면 기껏해야 2를 곱하는 것이기 때문에 이것은 그냥 더하기로 구현이 가능하기 때문에

- 큰 정수의 덧셈을 구하는 함수만 작성하여 해결하였습니다.

2. 주의사항

- 일단 dp[0]=1 입니다 (  nCo = 1 인 것과 같이) -- 아무것도 선택 안함

- 그리고 처음에 while(EOF) 를 이용하여 입력을 제어 했는데, 출력초과가 계속 나와서 

- 이부분을 , while (cin>>n)로 해결했습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;




vector<int> bigintadd(vector<int> v1, vector<int> v2) {

	if (v1.size() < v2.size()) { // v1이 항상 더 큰수
		vector<int> tmpv = v1; v1 = v2; v2 = tmpv;
	}
	vector<int> result(v1.size());
	for (int i = 0; i < v1.size(); i++) {
		result[i] = 0;
	}
	if (v1.size() == v2.size() && (v1[v1.size() - 1] + v2[v2.size() - 1]) >= 10) {
		result.push_back(0); //사이즈 하나 증가
	}

	for (int i = 0; i < v2.size(); i++) {
		int tmpi = v1[i] + v2[i]+result[i];
		if (tmpi >= 10) { result[i + 1] += 1; result[i] =( tmpi-10); }
		else result[i] = tmpi;
	}
	for (int i = v2.size(); i < v1.size(); i++) {
		result[i] += v1[i];
	}

	return result;
}

// 점화식 dp[i]=dp[i-1]+dp[i-2]*(3-1)
// 큰수의 곱을 구현해야 한다.

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	vector<int> dp[251];
	dp[0].push_back(1); dp[1].push_back(1); dp[2].push_back(3);
	for (int i = 3; i <= 250; i++) {
		dp[i] = bigintadd(dp[i - 1], bigintadd(dp[i - 2], dp[i - 2])); //8은 171 7은 85   171+85+85
	}
	int n;
	while (cin>>n) {
		for (int i = dp[n].size() - 1; i >= 0; i--) {
			cout << dp[n][i];
		}
		cout << "\n";
	}
	return 0;
}

www.acmicpc.net/problem/11652

1. 풀이방법

- 정렬을 하고 , 앞에서부터 쭉 살피면서 연속된 수를 체크하고 교체 및 갱신을 수행한다.

- 값의 범위는 -2^64 ~ 2^64 까지 이므로 대략 10^19정도 이므로 카드의 값은 long long 타입을 사용해주자

- 값을 오름차순으로 정렬을 해준 후 작업을 수행

2. 주의사항

- 첫번째, 값이 달라질때만 갱신작업을 수행하므로 배열의 마지막이 왔을때는 비교작업을 한번 수행해주어야 한다.

- 두번쨰, 카드가 1개일 때를 생각해보면 maxcount=1, resultvalue=cardset[0]로 초기화 하자 

  (n이 1이면 for 문을 돌지 않으므로 ---> 100% 쯤에서 틀렸습니다가 나오면 이 문제)

- 물론 주의사항은 모두 구현 방식에 따라 다를 수 있습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int n;
long long cardset[100001];
int maxcount;
long long resultvalue;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> cardset[i];
	}
	sort(cardset, cardset + n);
	maxcount = 1;
	resultvalue = cardset[0];
	int tmpcount = 1;
	for (int i = 1; i < n; i++) {
		if (cardset[i] == cardset[i - 1]) { 
			tmpcount++;
			if (i == n - 1) { //달라질때에만 값을 갱신하므로 , 마지막은 따로 계산해주어야함
				if (tmpcount > maxcount) { //같을때는 갱신하지 않는다.
					maxcount = tmpcount; resultvalue = cardset[i];
				}
			}
		}
		else {  
			if (tmpcount > maxcount) { //같을때는 갱신하지 않는다.
				maxcount = tmpcount; resultvalue = cardset[i - 1]; 
			}
			tmpcount = 1; }
	}
	cout << resultvalue;
	return 0;
}

www.acmicpc.net/problem/1837

1. 풀이방법

- 첫번째는 소수 판별과 두번째는 longlong 범위를 넘어가는 big integer에 대한 mod연산 구현

- 이 두가지를 구현하는 문제 인데 첫번째는 에라토스테네스의 채를 이용하여 소수 set을 만들었고 (k의최대값까지)

- string으로 큰수를 받아서 (10^100 이므로) c++에서 제공하는 정수를 담는 자료형으로는 어림도 없으므로

- 그 문자열로 받은 큰 수를 int로 나누어보는 함수를 구현하였다 (나누는 수는 k보다 작으므로 int 가능)

2. 주의사항

- 제 구현에서는 소수 set을 만드는 부분과 나누어지는지 확인하는 부분이 나누어져있지만

- 짜고 나서 보니 에라토스테네스의 체를 이용하여 구해가면서 그때그때 판별을 하면 연산의 수를 줄일 수 있을

- 것 같습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;
const int maxk= 1e6+1;

bool isitprime[maxk]; //false 이면 소수
string ps;
int k;
int resulti = 0;

void makeprimeset() { //소수 판별
	isitprime[0] = true; isitprime[1] = true;
	for (int i = 2; i <= k; i++) {
		if (isitprime[i] == false) { //소수이면
			int index = i;
			int tmp = 2;
			while (index * tmp <= k) { //배수는 모두 소수가 아님
				isitprime[index * tmp] = true;
				tmp++;
			}
		}
	}
}
bool bigintdivide(int p) {
	int tmpsum = 0;
	for (int i = 0; i < ps.length(); i++) {
		tmpsum = (tmpsum * 10 + (ps[i] - '0'))%p; //앞자리수 부터
	}
	if (tmpsum == 0) return true;
	else return false;
}

bool isunderk() {
	for (int i = 2; i <k; i++) {
		if (isitprime[i] == false) {
			if (bigintdivide(i)) {
				resulti = i; return false;
			}
		}
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> ps >> k;

	makeprimeset(); //에라토스테네스의 채
	if (isunderk()) cout << "GOOD" << "\n";
	else cout << "BAD" << " " << resulti << "\n";


	return 0;
}