굳건하게

문제 : https://www.acmicpc.net/problem/1182

[알고리즘풀이]

백트레킹을 이용해 만들 수 있는 모든 부분수열의 합을 구해본다.

#include<iostream>
#include<vector>

using namespace std;

int n_l[20], answer,n,m;

void bt(int i, int j, vector<int> v) {
	if (v.size() == i) {
		int temp = 0;
		for (int k = 0; k < i; k++){
			temp += v[k];
		}
		if (temp == m) {
			answer++;
		}
		return;
	}
	for (int k = j + 1; k < n; k++){
		v.push_back(n_l[k]);
		bt(i, k, v);
		v.pop_back();
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> n_l[i];
	for (int i = 1; i <= n; i++) {
		// i개 씩 뽑을거다.
		for (int j = 0; j < n + 1 - i; j++) {
			// j까지담김
			vector<int> v;
			v.push_back(n_l[j]);
			bt(i, j, v);
			v.pop_back();
		}
	}
	cout << answer;
}

문제 : https://www.acmicpc.net/problem/1788

[알고리즘풀이]

음수 N의 피보나치 값 F(N) = F(N + 2) - F(N + 1) 을 통해 구할 수 있고,

양수 N의 피보나치 값 F(N) = F(N - 1) + F(N - 2) 를 통해 구할 수 있습니다.

#include<iostream>

using namespace std;

#define j 1000000
#define m 1000000000
int f[2000001];

int abs(int n) {
	if (n < 0)
		return -n;
	return n;
}
int main(void) {
	f[j + 0] = 0, f[j + 1] = 1;

	int n;
	cin >> n;
	if (n >= 2) {
		for (int i = 2; i <= n; i++)
			f[i + j] = (f[i - 1 + j] + f[i - 2 + j]) % m;
	}
	else if (n < 0) {
		for (int i = -1; i >= n; i--)
			f[i + j] = (f[i + 2 + j] - f[i + 1 + j]) % m;
	}
	if (f[n + j] < 0) {
		cout << "-1\n" << abs(f[n + j]);
	}
	else if (f[n + j] > 0) {
		cout << "1\n" << abs(f[n + j]);
	}
	else
		cout << "0\n" << abs(f[n + j]);
}

문제 : https://www.acmicpc.net/problem/17298

[알고리즘풀이]

스택을 어떻게 활용해야될지 감이 오지 않아, 친구의 도움으로 해결할 수 있었습니다.

* 입력의 역순으로 순회하며 알고리즘을 진행합니다. *

1. 현재 값이 Stack의 Top보다 작다면 Stack의 Top이 NGE 값이 된다.

2. 현재 값이 Stack의 Top보다 크거나 같다면 Stack을 Pop하고 다시 1번부터 진행.

3. 현재 Stack이 비어있다면, 현재 값의 NGE 값은 -1이 됩니다.

4. 1,2,3번이 실행되고나면 Stack에 Push 해줍니다.

ex)

#include<iostream>
#include<stack>

using namespace std;

int a[1000000];
int l[1000000];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	stack<int> s;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> l[i];

	for (int i = n - 1; i >= 0; i--) {
		while ( !s.empty() && s.top() <= l[i])
			s.pop();

		if (s.empty())
			a[i] = -1;
		else
			a[i] = s.top();

		s.push(l[i]);
	}

	for (int i = 0; i < n; i++)
		cout << a[i] << ' ';
}

문제 : https://www.acmicpc.net/problem/1874

[알고리즘풀이]

1. 현재 스택의 Top보다 큰 값이 들어온다면, 그 수까지 스택을 Push하고 Push한 수들은 check를 한다.

  ( 이미 Push했던 수들은 다시 Push하면 안되므로 )

2. 현재 스택의 Top과 같은 값이 들어온다면, 스택을 Pop한다.

3. 현재 스택의 Top보다 작은 값이 들어온다면, "NO"를 출력한다.

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

int list[100001];
bool c[100001];
stack<int> s;
string answer;

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

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++){
		cin >> list[i];
	}

	s.push(0);

	for (int i = 1; i <= n; i++) {
		if (s.top() == list[i]) {
			s.pop();
			answer += '-';
			continue;
		}
		if (s.top() < list[i]) {
			for (int j = s.top() + 1; j <= list[i]; j++){
				if(c[j] == false){
					s.push(j);
					c[j] = true;
					answer += '+';
				}
			}
			s.pop();
			answer += '-';
			continue;
		}
		if (s.top() > list[i]) {
			cout << "NO\n";
			return 0;
		}
	}
	for (int i = 0; i < answer.length(); i++)
		cout << answer[i] << '\n';
}