이코테) 개미전사

 

https://velog.io/@corone_hi/108.-%EA%B0%9C%EB%AF%B8-%EC%A0%84%EC%82%AC

108. 개미 전사

 

DP문제인데, DFS가 생각나서  DFS 로 풀었음, 근데 순열로 이루어짐, 조합으로 해야하는데 아이디어가 생각나지 않음(진행중)

즉 1,2,3,4  에서 1, 3 과 3, 1  경우의수 중 하나만 나오게 하려함.

 

#include<iostream>
//recursion 이용.  
//branch ,level 모두 n.
#include<string>
#include<vector>
using namespace std;

int n;
int arr[100];
int path[100];
int check[100]{0,};// 자기 자신과 그 주변(-1, 1 인덱스 접근하는거 차단)
int Max = -2 * 10e7;

int visited[100]{ 0, }; // 조합목적 즉 1,4  4,1 중복 나오게 안할거 근데 이건 속도를 높일 수 있다. 속도 상관안하면, 어차피 맥스값만 구하면 되기에 무시해도 좋다. 다만, 속도향상을 해야한다.
void recursion(int level, int sum) {
	
	if (n%2==0&&(n/2)==level) {//n갯수 짝수
		for (int x = 0; x < level; ++x) {
			cout << path[x]<<" ";
		}
		if (sum > Max) Max = sum;
		return;
	}
	else if (n % 2 == 1 && ((n / 2) + 1) == level) // n갯수 홀수
	{
		if (sum > Max) Max = sum;
		for (int x = 0; x < level; ++x) {
			cout << path[x]<<" ";
		}
		cout << endl;
		return;
	}
	for (int x = 0; x < n; ++x) {
		if (check[x] > 0||check[x+1]>0)continue; // 자기자신과 그 다음 인덱스 1인 경우
		if (x != 0) {
			if (check[x - 1] > 0) continue;//버그해결 // x가 0이 아니면 자기자신의 -1인덱스가 1인 경우
		}
		check[x] = 1;
		if (x != 0) if (check[x - 1] == 1)continue;
		
		path[level] = arr[x];
		recursion(level + 1,sum+path[level]);
		check[x] = 0;
		path[level] = 0;
	}
}

int main(void) {
	cin >> n;
	for (int x = 0; x < n; ++x) {
		cin >> arr[x];
	}
	recursion(0,0);

	cout << "답: " << Max << endl;
}

 

 

동빈나

DP

#include <bits/stdc++.h>

using namespace std;

// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
int d[100];
int n;
vector<int> arr;

int main(void) {
    // 정수 N을 입력받기
    cin >> n;
    // 모든 식량 정보 입력받기
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
    d[0] = arr[0];
    d[1] = max(arr[0], arr[1]);
    for (int i = 2; i < n; i++) {
        d[i] = max(d[i - 1], d[i - 2] + arr[i]);
    }

    // 계산된 결과 출력
    cout << d[n - 1] << '\n';
}