급하게임개발

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

이 문제의 경우 쉽다  dfs 는 자기 자식으로 쭉내려가기 때문에 일단 자기 자식들중 방문하지 않은 자식있으면 재귀로 쭉쭉내려간다 갈 수 없는곳을 만나면 자기 부모로 돌아가 갈 수 있는 곳을 다시 탐색하는걸 반복한다 그렇기 때문에 일단 재귀로 콜한다음 자기자식이 방문했는지 아닌지 검사하고 방문했으면 conitnue 문을 통해 방문을 건너뛴다 재귀기 때문에 갈곳이 없어 리턴되면 자기자신의 부모가 갈곳을 탐색한다 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> vertex[200001];
int visitednum[100001];
bool visited[100001] = { false, };
int countnum = 0;
void dfs(int start) {
	countnum += 1;
	visitednum[start] = countnum;
	visited[start] = 1;
	for (int i = 0; i < vertex[start].size(); i++) {
		if (visited[vertex[start][i]] == true) {
			continue;
		}
		dfs(vertex[start][i]);
	}
}
int main() {
	int vertexnum, edgenum, startvertex;
	cin >> vertexnum >> edgenum >> startvertex;
	for (int i = 1; i <= edgenum; i++) {
		int temp1 = 0;
		int temp2 = 0;
		cin >> temp1 >> temp2;
		vertex[temp1].push_back(temp2);
		vertex[temp2].push_back(temp1);
	}
	for (int i = 1; i <= vertexnum; i++) {
		sort(vertex[i].begin(), vertex[i].end());
	}
	dfs(startvertex);
	for (int i = 1; i <= vertexnum; i++) {
		cout << visitednum[i]<<'\n';
	}

}

일단 위에 코드를 보게되면  visitednum이라는 것이 존재 한다 visitednum은 i번째가 루트로부터 몇번째에 갈 수 있는지를 visitednum[i] 에 저장 해준다 이것을 이용해 후에 답을 출력할 것이다. 개인적으로 배열을 써야하는 알고리즘 문제들은 visualstudio에서 stack 사이즈 문제로 오류를 엄청 띄우기 때문에 거의 전역으로 설정 해주는게 좋다. 뭐 다음 코드는 이전글에 있는 DFS BFS 알고리즘 문제에 있는 방식과 똑같다 나랑연결되 있는애들을 나의 vertex에 넣어 준다. 

예시로 백준에 input값을 보자

5 5 1
1 4
1 2
2 3
2 4
3 4

이런식으로 입력을 받아오면

vertex[1]에는 4,2

vertex[2]에는 1,3,4

vertex[3]에는 2,4

vertex[4]에는 1,2,3

이 들어가게 된다 DFS에서의 간선은 양방향으로 갈수 있기때문에 양쪽에 값을 넣어 준 것 이다. 그 이후에  이 vector를 오름차 순으로 정렬해주고 나와 연결된애에게로 간다 지금 상황에선 2부터 쭉가서 끝까지 간다 쭉가다가 더 이상 갈 수 없으면 재귀함수는 return으로 자기 caller에게 돌아가기 때문에 자기 부모로 돌아가게된다 그후 부모도 다른 곳으로 갈 수 있는 지 없는지 판단하고 자기자신의 부모로 간다 이렇게 반복되어  DFS가 완성된다

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

dp문제는 풀 때 마다 점화식이 중요하다고 생각되어진다 역시 이번 문제도 점화식인데

이번문제의 경우 기존에 올렸던과는 다르게 3개의 후보중 하나를 뽑는 방식으로 생각해주어야 한다

그이유는 이번 문제에서 핵심적인 내용이 연속으로 3개의 포도주를 못마신다는 거였으니  그거를 이용해서 풀어야 한다

1.O O X O

2.O X O O

3.X O O X

이문제는 위에처럼 3가지 경우의 수가 존재 한다 즉 N번째 와인이 존재한다고 가정했을때 N번째 와인을 마신다고 가정했을때 첫번째로 마시냐 두번째로 마시냐 혹은 안마시냐 이렇게 3개의 경우의 수가 존대 한다. 이를 점화식으로 나타내면

1은 dp[j-2]+arr[j];

2는 dp[j-3]+arr[j-1]+arr[j]

3은 dp[j-1]

이다 1은 j번째 포도주를 먹기로 가정했기 때문에 내이전은 못마시고 나보다 2개전에 있는 애를 마실 수 있다

2는 나도 마시고 내이전도 마신다고 가정한것이다 

마지막은 나를 안마셨기 때문에 나의 이전까지의 최대값만 필요하다 어차피 이렇게 우리가 3개의 식으로 나눴을 경우 3잔을 연속으로 마시는 경우의 수는 발생하지 않는다

#include <iostream>
#include <algorithm>
using namespace std;
int dp[10001];
int arr[10001];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];

	for (int j = 3; j <= n + 1; j++) {
		dp[j] = dp[j - 1];
		dp[j] = max(dp[j], dp[j - 2] + arr[j]);
		dp[j] = max(dp[j], dp[j - 3] + arr[j - 1] + arr[j]);

	}
	cout << dp[n] << endl;
}