C++ / 2240 / 자두나무 ( 다이나믹 프로그래밍 )

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

문제 요약

자두는 자두를 좋아합니다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 합니다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 합니다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문입니다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 됩니다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있습니다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없습니다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 합니다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성해야합니다. 자두는 1번 자두나무 아래에 위치해 있다고 합니다.

문제 풀이 1

이 문제는 같이 공부하는 형이 추천해줘서 풀게되었는데, 

처음엔 완탐으로 풀어보았습니다.

 

처음 도전했을때는 백트래킹으로 접근할려다가 어려움이 있어 결국 포기...

다시 공부해서 완탐으로 재도전 하였습니다.

 

다시 보면 몇줄안되는데 재귀함수도 서툴고 완전탐색 숙련도가 모잘라서 그런지 어려움이 있었음..

 

 

1. 완전탐색 함수를 만들어 탐색합니다.

2. 함수 인자로는 현재 나무 ( 1번인지 2번인지 ), 경과하는 초( treeCnt ), 이동 횟수 (  w ), 획득한 자두의 개수

3. 중단점으로는 이동횟수가 0보다 작으면 반환합니다. 

4. 경과하는 초가 끝까지 갔으면 현재 자두 값과 기존 자두값 중 큰 값을 저장합니다.

5. 재귀 호출 하는데,  위치를 변경하는 경우는 현재 나무에 xor 연산을 해줍니다. ( 자두나무 위치를 1과 2로 받았는데 편의상  0과  1로 사용합니다. ), 경과하는 초를 1 증가해주고 이동 횟수를 감소시킵니다. 획득한 자두의 개수는 현재 항이 자두 나무의 위치와 일치하는지 == 연산을 하여 더해줍니다.

6. 변경하지 않는 경우는 x를 그대로 사용하고 이동 횟수를 감소시키지 않습니다.

7. 역대 값중 가장 큰값이 저장되어있을 ans를 출력합니다.

코드 1

// 완전 탐색

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


int t, w, ans = 0;

vector<int>v;


void go(int x, int treeCnt, int moveStep, int value)
{
    // 중단점
    if (moveStep < 0)
    {
        return;
    }
    if (treeCnt == t)
    {
        // 끝까지 갔을경우 기존값과 비교하여 큰값 저장
        ans = max(ans, value);
        return;
    }

    // 위치를 변경하는 경우
    go(x ^ 1, treeCnt + 1, moveStep - 1, value + ((v[treeCnt] - 1) == x));
    // 변경 하지 않는 경우
    go(x, treeCnt + 1, moveStep, value + ((v[treeCnt] - 1) == x));

}
int main()
{
    cin >> t >> w;

    for (int i = 0; i < t; i++)
    {
        int a;
        cin >> a;
        v.push_back(a);
    }
    // 처음 위치를 변경하지않는 경우
    go(0, 0, w, 0);
    // 변경하는 경우
    go(1, 0, w - 1, 0);
    cout << ans;
    return 0;
}

 

주의할 점

완전 탐색 (브루투포스)은 말 그대로  모든 경우의 수를 탐색하기 때문에 시간 복잡도가 높습니다.

또한 재귀를 사용하기 때문에 중단점을 잘 걸어주지 않으면 무한루프에 빠지기 쉽습니다.

 

XOR 연산을 적극 활용하도록 해야겠습니다.

예제

7 2
2
1
1
2
2
1
1

결과

문제 풀이 2

https://blog.naver.com/maison_ours/223782158717

완전탐색 알고리즘 개념 정리

이 논리에 따르면 완탐으로 시간복잡도가 초과가 되는 문제는 DP알고리즘으로 풀 수 있다고 합니다.

확인한 경우의 수는 배열( DP 배열 ) 저장해두어 중복탐색을 방지하여 시간복잡도를 줄일 수 있습니다.

 

1. 기존에 작성하였던 완전탐색 함수에서 변형을 해야합니다. 함수는 반환값이 있어야하고 매개변수에 value는 빼줍니다.( 값은 배열에 저장할것이기 때문에 )

2. 결과들을 담을 dp 변수를 만들어  줍니다. 배열은 매개변수개수와 동일한 사이즈로 만들어줍니다. ( 모든 경우의수가 매개변수에 따라 생기기 때문 )

3. 만들어진 dp배열은 경우의수가 아직 들어있지 않은 ( 방문하지 않은 ) 경우를 체크하기 위해 -1로 초기화해 줍니다.

4. 함수 내에서는 중단점일 경우에 0을 반환합니다.

5. 중단점이 아닐경우에는 메모이제이션으로 현재 경우의수 배열을 참조 변수에 담습니다.

6. 참조변수의 값이 -1이아니라면 이미 값이 들어 있는 탐색을 마친 배열이기 때문에 값을 반환하여줍니다.

7. 탐색하지 않은 경우는 참조 변수에  위치를 변경하는 것과 변경하지 않는 경우중 더 큰값으로 저장하고 반환합니다.

8. 출력 부분은 위치를 변경하는 경우와 아닌 경우중 더 큰 값을 반환시킵니다.

주의할 점

dp 배열을 -1로 꼭 초기화 하여 탐색하지 않은 경우와 탐색한 경우를 구분해야 합니다.

메모이제이션 사용에 주의 해야합니다.

코드 2

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


int t, w;

vector<int>v;
// 결과를 담아둘 dp 배열
int dp[4][1004][34];

int go(int x,int treeCnt, int moveStep)
{
	//중단점
	if (moveStep < 0)
	{
		return 0;
	}
	if (treeCnt == t)
	{
		return 0;
	}
	// 메모이제이션
	int& ret = dp[x][treeCnt][moveStep];
	// 이미 계산완료 되었으면 값 반환
	if (ret != -1)
	{
		return ret;
	}
	// 계산 하지 않았으면 계산
	// 위치를 변경하는것과 변경하지 않는 경우중 더 큰 값으로 저장
	ret = max(go(x, treeCnt+1, moveStep),go(x^1,treeCnt+1,moveStep-1)) + ((v[treeCnt]-1) == x);
	// 결과 반환
	return ret;
	
}
int main()
{
	cin >> t >> w;

	for (int i = 0; i < t; i++)
	{
		int a;
		cin >> a;
		v.push_back(a);
	}
	// 방문하지 않는 경우를 체크하기 위해 -1로 초기화
	memset(dp, -1, sizeof(dp));
	// 처음에 바꾸면서 시작하는것과 아니것 중 더 큰값
	cout << max(go(0, 0, w), go(1, 0, w-1));
	return 0;
}

예제

7 2
2
1
1
2
2
1
1

결과