728x90

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

 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
int n;
int s;
vector<int> v;
int cnt = 0;

void combination(vector<bool> visited, vector<pair<int, int>> result, int num, int k) {
	if (num == k) {
		int total = 0;
		for (int i = 0; i < result.size(); i++) {
			total += result[i].first;
		}
		if (total == s) cnt++;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (num == 0) {
			if (!visited[i]) {
				visited[i] = true;
				result[num].first = v[i];
				result[num].second = i;
				combination(visited, result, num + 1, k);
				visited[i] = false;
			}
		}
		else {
			if (result[num - 1].second < i && !visited[i]) {
				visited[i] = true;
				result[num].first = v[i];
				result[num].second = i;
				combination(visited, result, num + 1, k);
				visited[i] = false;
			}
		}
	}
}


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n >> s;
	v = vector<int>(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	for (int i = 1; i <= n; i++) {
		vector<bool> visited(n);
		vector<pair<int, int>> result(i);
		combination(visited, result, 0, i);
	}
	cout << cnt;
	return 0;
}

pair의 second에는 인덱스를 넣어주었다.

728x90
728x90

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

 

4948번: 베르트랑 공준

문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) n이 주어졌을 때, n보다 크고, 2n보

www.acmicpc.net

n이 소수인지 아닌지 알아보려면 제곱근 n까지만 나눠보면 된다.

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


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	while (true) {
		int n;
		cin >> n;
		if (n == 0) break;
		int count = 0;
		for (int num = n + 1; num <= 2 * n; num++) {
			bool flag = true;
			if (num % 2 == 1) {
				for (int i = 3; i <= sqrt(num); i++) {
					if (num % i == 0) {
						flag = false;
						break;
					}
				}
			}
			else {
				flag = false;
			}
			if (num == 2) flag = true;
			if (num == 1) flag = false;
			if (flag) count++;
		}
		cout << count << '\n';
	}
	return 0;
}

 

728x90
728x90

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

 

3671번: 산업 스파이의 편지

문제 안녕하세요. 저는 산업 스파이입니다. 저의 정체를 절대 다른 사람에게 말하지 말아주세요. 저의 가장 최근 일은 유명한 수학 연구소의 최신 연구 결과를 훔쳐오는 것이었습니다. 저는 매우 유능한 산업 스파이이기 때문에, 연구 결과를 어렵지 않게 얻을 수 있었습니다. 하지만, 제가 올 것을 미리 알았는지 연구소에서는 연구 결과를 모두 서류 절단기에 넣어버렸습니다. 어쩔수 없이 저는 눈물을 머금고 종이 조각을 모두 훔쳐왔습니다. 저를 고용한 사람은 매우 무

www.acmicpc.net

비주얼 스튜디오에서는 sqrt() 함수가 잘 동작해서 그대로 제출했는데 컴파일 에러가 났다.

비주얼 스튜디오에서는 에러가 없어도 <cmath>를 꼭 포함하는거 잊지 말자

그리고 소수 구할 때 n / 2까지 나눠보지 않아도 루트 n까지만 나눠봐도 된다. 이걸 몰라서 계속 시간초과가 났다.

절대 잊지 말자.

소수인지 아닌지 판별할 때에는 n / 2까지 굳이 나눠보지 않아도 루트 n까지 나눠보면 된다

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

set<int> st;

void combination(vector<bool> visited, vector<int> result, int n, int k, int num, int* arr) {
	if (num == k) {
	
		do {
			string str = "";
			for (int i = 0; i < k; i++) {
				str += (result[i] + '0');
			}
			int number = stoi(str);
			bool flag = true;
			if (number % 2 == 1) {
				for (int i = 2; i <= sqrt(number); i++) {
					if (number % i == 0) {
						flag = false;
						break;
					}
				}
			}
			else {
				flag = false;
			}
			if (number == 1 || number == 0) flag = false;
			if (number == 2) flag = true;
			if (flag) {
				st.insert(number);
			}

		} while (next_permutation(result.begin(), result.end()));
		return;
	}
	for (int i = 0; i < n; i++) {
		if (num == 0) {
			if (!visited[i]) {
				visited[i] = true;
				result[num] = arr[i];
				combination(visited, result, n, k, num + 1, arr);
				visited[i] = false;
			}
		}
		else {
			if (!visited[i] && result[num - 1] <= arr[i]) {
				visited[i] = true;
				result[num] = arr[i];
				combination(visited, result, n, k, num + 1, arr);
				visited[i] = false;
			}
		}
	}
}

int main() {
	int c;
	cin >> c;
	for (int t = 0; t < c; t++) {
		st.clear();
		string s;
		cin >> s;
		int* arr = new int[7];
		for (int i = 0; i < s.size(); i++) {
			arr[i] = s[i] - '0';
		}
		sort(arr, arr + s.size());
		for (int i = 1; i <= s.size(); i++) {
			vector<bool> visited(s.size());
			vector<int> result(i);
			combination(visited, result, s.size(), i, 0, arr);
		}
		cout << st.size() << '\n';
	}
	return 0;
}
728x90
728x90

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

 

11006번: 남욱이의 닭장

문제 계란집을 운영하는 남욱이는 매일 닭장에서 달걀을 수거해간다. 어느 날 닭장에 들어가보니 일부 닭의 다리가 하나씩 사라졌다. 남욱이는 얼마나 많은 닭들이 한 다리를 잃었는지 알고싶었지만 닭이 너무 많아 셀 수 없었고, 대신 모든 닭의 다리수를 셌다. 고민하는 남욱이를 위해 모든 닭의 다리수의 합과 닭의 수를 가지고 이것을 해결해주자. 입력 첫째 줄에 총 테스트 케이스의 수 T (T ≤ 25)가, 둘째 줄 부터 T + 1째줄까지 매줄 마다 모든 닭의 다

www.acmicpc.net

#include <iostream>
using namespace std;


int main() {
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		int allLegsCount;
		int numOfChickens;
		cin >> allLegsCount >> numOfChickens;
		cout << numOfChickens * 2 - allLegsCount << " " << numOfChickens - (numOfChickens * 2 - allLegsCount) << '\n';
	}
	return 0;
}
728x90
728x90

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

 

3187번: 양치기 꿍

문제 양치기 꿍은 맨날 늑대가 나타났다고 마을 사람들을 속였지만 이젠 더이상 마을 사람들이 속지 않는다. 화가 난 꿍은 복수심에 불타 아예 늑대들을 양들이 있는 울타리안에 마구 집어넣어 양들을 잡아먹게 했다. 하지만 양들은 보통 양들이 아니다. 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다. 물론 그 외의 경우는 양이 전부 잡아먹히겠지만 말이다. 꿍은 워낙 똑똑했기 때문에 이들의 결과는 이미 알고있다. 만약 빈

www.acmicpc.net

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


int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<char>> arr(n, vector<char>(m));
	vector<vector<bool>> visited(n, vector<bool>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == '#') visited[i][j] = true;
		}
	}
	int surviveSheep = 0;
	int surviveWolf = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!visited[i][j]) {
				int wolf = 0;
				int sheep = 0;
				queue<pair<int, int>> q;
				q.push(make_pair(i, j));
				while (!q.empty()) {
					pair<int, int> cur = q.front();
					q.pop();
					if (!visited[cur.first][cur.second]) {
						visited[cur.first][cur.second] = true;
						if (arr[cur.first][cur.second] == 'v') wolf++;
						else if (arr[cur.first][cur.second] == 'k') sheep++;
						if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second]) {
							q.push(make_pair(cur.first - 1, cur.second));
						}
						if (cur.first + 1 < n && !visited[cur.first + 1][cur.second]) {
							q.push(make_pair(cur.first + 1, cur.second));
						}
						if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1]) {
							q.push(make_pair(cur.first, cur.second - 1));
						}
						if (cur.second + 1 < m && !visited[cur.first][cur.second + 1]) {
							q.push(make_pair(cur.first, cur.second + 1));
						}
					}
				}
				if (sheep > wolf) {
					surviveSheep += sheep;
				}
				else {
					surviveWolf += wolf;
				}
			}
		}
	}
	cout << surviveSheep << " " << surviveWolf;
	return 0;
}
728x90
728x90

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

 

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

www.acmicpc.net

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


int main() {
	int numOfNode, numOfEdge;
	cin >> numOfNode >> numOfEdge;
	vector<int> graph[1001];
	for (int i = 0; i < numOfEdge; i++) {
		int from, to;
		cin >> from >> to;
		graph[from].push_back(to);
		graph[to].push_back(from);
	}
	vector<bool> visited(numOfNode + 1);
	int count = 0;
	for (int i = 1; i <= numOfNode; i++) {
		if (!visited[i]) {
			queue<int> q;
			q.push(i);
			while (!q.empty()) {
				int cur = q.front();
				q.pop();
				if (!visited[cur]) {
					visited[cur] = true;
					for (int j = 0; j < graph[cur].size(); j++) {
						if (!visited[graph[cur][j]])
							q.push(graph[cur][j]);
					}
				}
			}
			count++;
		}
	}
	cout << count;
	return 0;
}
728x90
728x90

삼성 SW 역량 테스트 기출 문제

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

 

17779번: 게리맨더링 2

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다

www.acmicpc.net

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

int n;
vector<vector<int>> population;
vector<int> difference;

void select(vector<int> result, int num) {
	if (num == 4) {
		int x = result[0];
		int y = result[1];
		int d1 = result[2];
		int d2 = result[3];
		if (x + d1 + d2 >= n) return;
		if (y - d1 < 0) return;
		if (y + d2 >= n) return;
		if (d1 == 0 || d2 == 0) return;
		vector<vector<int>> map(n, vector<int>(n));
		for (int i = 0; i <= d1; i++) {
			map[x + i][y - i] = 5;
		}
		for (int i = 0; i <= d2; i++) {
			map[x + i][y + i] = 5;
		}
		for (int i = 0; i <= d2; i++) {
			map[x + d1 + i][y - d1 + i] = 5;
		}
		for (int i = 0; i <= d1; i++) {
			map[x + d2 + i][y + d2 - i] = 5;
		}
		for (int i = 1; ; i++) {
			if (x - i >= 0) map[x - i][y] = 1;
			else break;
		}
		for (int i = 1; ; i++) {
			if(y + d2 + i < n) map[x + d2][y + d2 + i] = 2;
			else break;
		}
		for (int i = 1; ; i++) {
			if (y - d1 - i >= 0) map[x + d1][y - d1 - i] = 3;
			else break;
		}
		for (int i = 1; ; i++) {
			if (x + d1 + d2 + i < n) map[x + d1 + d2 + i][y - d1 + d2] = 4;
			else break;
		}
		for (int i = 0; i < n; i++) {
			if (map[i][0] != 0) break;
			for (int j = 0; j < n; j++) {
				if (map[i][j] != 0) break;
				map[i][j] = 1;
			}
		}
		for (int i = 0; i < n; i++) {
			if (map[i][n - 1] != 0) break;
			for (int j = n - 1; j >= 0; j--) {
				if (map[i][j] != 0) break;
				map[i][j] = 2;
			}
		}
		for (int i = n - 1; i >= 0; i--) {
			if (map[i][0] != 0) break;
			for (int j = 0; j < n; j++) {
				if (map[i][j] != 0) break;
				map[i][j] = 3;
			}
		}
		for (int i = n - 1; i >= 0; i--) {
			if (map[i][n - 1] != 0) break;
			for (int j = n - 1; j >= 0; j--) {
				if (map[i][j] != 0) break;
				map[i][j] = 4;
			}
		}

		int sum[5] = { 0 };
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				switch (map[i][j]) {
				case 0:
				case 5:
					sum[4] += population[i][j]; break;
				case 1:
					sum[0] += population[i][j]; break;
				case 2:
					sum[1] += population[i][j]; break;
				case 3:
					sum[2] += population[i][j]; break;
				case 4:
					sum[3] += population[i][j]; break;
				}
			}
		}
		int minPopulation = 40000;
		int maxPopulation = 0;
		for (int i = 0; i < 5; i++) {
			if (sum[i] < minPopulation) minPopulation = sum[i];
			if (sum[i] > maxPopulation) maxPopulation = sum[i];
		}
		difference.push_back(maxPopulation - minPopulation);
		return;
	}
	for (int i = 0; i < n - 1; i++) {
		result[num] = i;
		select(result, num + 1);
	}
}


int main() {
	cin >> n;
	population = vector<vector<int>>(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> population[i][j];
		}
	}
	vector<int> result(4);
	select(result, 0);
	int totalMin = 40000;
	for (int i = 0; i < difference.size(); i++) {
		if (difference[i] < totalMin) totalMin = difference[i];
	}
	cout << totalMin;
	return 0;
}
728x90
728x90

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

 

17471번: 게리맨더링

선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.

www.acmicpc.net

조합(combination)과 bfs로 풀었다.

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

int n;
vector<int> w[10];
vector<int> difference;
vector<int> population;

bool isMemberOf(vector<int> v, int num) {
	bool isIn = false;
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == num) {
			isIn = true;
			break;
		}
	}
	return isIn;
}

void divide(vector<bool> visited, vector<int> result, int count, int num) {
	if (count == num) {
		vector<int> others;
		for (int i = 0; i < n; i++) {
			bool found = false;
			for (int j = 0; j < result.size(); j++) {
				if (i == result[j]) {
					found = true;
					break;
				}
			}
			if (!found) others.push_back(i);
		}
		visited = vector<bool>(n);
		queue<int> q;
		q.push(result[0]);
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			visited[cur] = true;
			for (int i = 0; i < w[cur].size(); i++) {
				if (!visited[w[cur][i]] && isMemberOf(result, w[cur][i]))
					q.push(w[cur][i]);
			}
		}
		q.push(others[0]);
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			visited[cur] = true;
			for (int i = 0; i < w[cur].size(); i++) {
				if (!visited[w[cur][i]] && isMemberOf(others, w[cur][i]))
					q.push(w[cur][i]);
			}
		}
		bool allVisited = true;
		for (int i = 0; i < n; i++) {
			if (!visited[i]) {
				allVisited = false;
				break;
			}
		}
		if (allVisited) {
			int sumOfResult = 0;
			int sumOfOthers = 0;
			for (int i = 0; i < result.size(); i++) {
				sumOfResult += population[result[i]];
			}
			for (int i = 0; i < others.size(); i++) {
				sumOfOthers += population[others[i]];
			}
			difference.push_back(abs(sumOfResult - sumOfOthers));
		}
		return;
	}

	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			if (num == 0) {
				visited[i] = true;
				result[num] = i;
				divide(visited, result, count, num + 1);
				visited[i] = false;
			}
			else {
				if (result[num - 1] < i) {
					visited[i] = true;
					result[num] = i;
					divide(visited, result, count, num + 1);
					visited[i] = false;
				}
			}
		}
	}
}

int main() {
	cin >> n;
	population = vector<int>(n);
	for(int i = 0; i < n; i++)
		cin >> population[i];
	for (int i = 0; i < n; i++) {
		int count;
		cin >> count;
		for (int j = 0; j < count; j++) {
			int to;
			cin >> to;
			w[i].push_back(to - 1);
		}
	}
	for (int i = 1; i <= n / 2; i++) {
		vector<bool> visited(n);
		vector<int> result(i);
		divide(visited, result, i, 0);
	}
	if (difference.size() > 0) {
		int minDiff = 1000;
		for (int i = 0; i < difference.size(); i++) {
			if (difference[i] < minDiff) minDiff = difference[i];
		}
		cout << minDiff;
	}
	else cout << -1;
	return 0;
}
728x90
728x90

삼성 SW 역량 테스트 기출 문제

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

 

14499번: 주사위 굴리기

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마

www.acmicpc.net

문제 그대로를 코드로 구현하면 된다. 다만 주의할 것은 좌표가 (x, y)가 아니라 (y, x)라는 것이다. 따라서 입력받을 때 y, x 순으로 받아야 한다. 나는 그래서 그냥 row, col로 받았다.

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

int n, m;
int dice[6] = { 0 };
vector<vector<int>> map;

void toNorth(int& nowRow, int& nowCol, int& floorIndex, int& ceilingIndex, int& westIndex, int& eastIndex, int& northIndex, int& southIndex) {
	if (nowRow - 1 < 0) return;
	int temp = floorIndex;
	floorIndex = northIndex;
	northIndex = ceilingIndex;
	ceilingIndex = southIndex;
	southIndex = temp;
	nowRow--;
	if (map[nowRow][nowCol] == 0) {
		map[nowRow][nowCol] = dice[floorIndex];
	}
	else {
		dice[floorIndex] = map[nowRow][nowCol];
		map[nowRow][nowCol] = 0;
	}
	cout << dice[ceilingIndex] << '\n';
}
void toSouth(int& nowRow, int& nowCol, int& floorIndex, int& ceilingIndex, int& westIndex, int& eastIndex, int& northIndex, int& southIndex) {
	if (nowRow + 1 >= n) return;
	int temp = floorIndex;
	floorIndex = southIndex;
	southIndex = ceilingIndex;
	ceilingIndex = northIndex;
	northIndex = temp;
	nowRow++;
	if (map[nowRow][nowCol] == 0) {
		map[nowRow][nowCol] = dice[floorIndex];
	}
	else {
		dice[floorIndex] = map[nowRow][nowCol];
		map[nowRow][nowCol] = 0;
	}
	cout << dice[ceilingIndex] << '\n';
}
void toEast(int& nowRow, int& nowCol, int& floorIndex, int& ceilingIndex, int& westIndex, int& eastIndex, int& northIndex, int& southIndex) {
	if (nowCol + 1 >= m) return;
	int temp = westIndex;
	westIndex = floorIndex;
	floorIndex = eastIndex;
	eastIndex = ceilingIndex;
	ceilingIndex = temp;
	nowCol++;
	if (map[nowRow][nowCol] == 0) {
		map[nowRow][nowCol] = dice[floorIndex];
	}
	else {
		dice[floorIndex] = map[nowRow][nowCol];
		map[nowRow][nowCol] = 0;
	}
	cout << dice[ceilingIndex] << '\n';
}
void toWest(int& nowRow, int& nowCol, int& floorIndex, int& ceilingIndex, int& westIndex, int& eastIndex, int& northIndex, int& southIndex) {
	if (nowCol - 1 < 0) return;
	int temp = floorIndex;
	floorIndex = westIndex;
	westIndex = ceilingIndex;
	ceilingIndex = eastIndex;
	eastIndex = temp;
	nowCol--;
	if (map[nowRow][nowCol] == 0) {
		map[nowRow][nowCol] = dice[floorIndex];
	}
	else {
		dice[floorIndex] = map[nowRow][nowCol];
		map[nowRow][nowCol] = 0;
	}
	cout << dice[ceilingIndex] << '\n';
}


int main() {
	int nowCol, nowRow, k;
	cin >> n >> m >> nowRow >> nowCol >> k;
	map = vector<vector<int>>(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	int floorIndex = 0;
	int eastIndex = 1;
	int ceilingIndex = 2;
	int westIndex = 3;
	int northIndex = 4;
	int southIndex = 5;
	for (int i = 0; i < k; i++) {
		int direction;
		cin >> direction;
		switch (direction) {
		case 1:
			toEast(nowRow, nowCol, floorIndex, ceilingIndex, westIndex, eastIndex, northIndex, southIndex);
			break;
		case 2:
			toWest(nowRow, nowCol, floorIndex, ceilingIndex, westIndex, eastIndex, northIndex, southIndex);
			break;
		case 3:
			toNorth(nowRow, nowCol, floorIndex, ceilingIndex, westIndex, eastIndex, northIndex, southIndex);
			break;
		case 4:
			toSouth(nowRow, nowCol, floorIndex, ceilingIndex, westIndex, eastIndex, northIndex, southIndex);
			break;
		}
	}
	return 0;
}
728x90
728x90

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

 

9507번: Generations of Tribbles

문제 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보나치를 만들었다. 꿍만의 피보나치 함수가 koong(n)이라고 할 때, n < 2 : 1 n = 2 : 2 n = 3 : 4 n > 3 : koong(n − 1) + koong(n − 2) + koong(n − 3) + koong(n − 4) 이다. 여러분도 꿍 피보나치

www.acmicpc.net

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


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int testCase;
	cin >> testCase;
	long long koong[68];
	koong[0] = koong[1] = 1;
	koong[2] = 2;
	koong[3] = 4;
	for (int i = 4; i < 68; i++) {
		koong[i] = koong[i - 1] + koong[i - 2] + koong[i - 3] + koong[i - 4];
	}
	for (int t = 0; t < testCase; t++) {
		int n;
		cin >> n;
		cout << koong[n] << '\n';
	}
	return 0;
}
728x90

+ Recent posts