[C/C++] 백준 3976번 - 역습 (DP)

 

문제

축구에서 역습은 매우 중요한 전술이다. WeissBlume FC는 수비 할 때, 스트라이커 두명을 제외하고는 모두 자기 진영에서 수비를 한다. 이때, 수비수가 상대방의 공을 따게 되면, 스트라이커에게 긴 패스를 하면서 역습을 시작한다. 두 스트라이커는 모두 서로가 어떻게 움직일지 알고 있고, 어떤 점에서는 다른 스트라이커에게 공을 패스할 수도 있다. 

이러한 상황에서 역습을 전개해가는 과정은 매우 다양하게 전개될 수 있다. 먼저, 수비수는 어떤 스트라이커에게 공을 연결해야 할지 결정을 해야 하고, 공을 소유하고 있는 스트라이커는 공을 드리블할지, 패스를 해야할지, 슛을 해야할지 결정을 해야 한다. 이런 4가지 행동(긴 패스, 드리블, 패스, 슛)은 실패할 수도 있다. 따라서, 감독은 이 모든 행동에 난이도를 계산했다.

WeissBlume FC가 이상적으로 경기를 진행할 때, 최소 난이도를 구하는 프로그램을 작성하시오.

위의 그림에서 수비는 왼쪽 진영의 X마크이다. 이때, 오른쪽 진영의 X는 스트라이커이다. 스트라이커는 미리 정해진 경로를 동시에 움직인다. 미리 지정해논 점(원)에서는 공을 드리블 해서 다음 점으로 이동할지, 다른 스트라이커에게 패스를 할 지 결정을 해야 한다. 마지막 점에서 스트라이커는 슛을 하면 된다.

입력

첫째 줄에 테스트 케이스의 개수 c가 주어진다. (1 ≤ c ≤ 100) 각각의 테스트 케이스는 다섯 줄로 이루어져 있다.

테스트 케이스의 첫째 줄에는 각 스트라이커가 이동하는 방법에서 미리 지정해논 점의 개수 n이 주어진다. (2 ≤ n ≤ 100,000) n 다음에는 l1, l2, s1, s2이 주어진다. l1과 l2은 수비수가 스트라이커에게 긴 패스를 할 때 난이도이고, s1과 s2은 스트라이커가 슛을 할 때의 난이도이다.

그 다음 줄에는 첫 번째 스트라이커가 i번 점에서 두 번째 스트라이커의 i+1번 점으로 패스를 할 때의 난이도 n-1개가 주어진다. 다음 줄에는 첫 번째 스트라이커가 i번 점에서 i + 1 드리블 할 때의 난이도 n-1개가 주어진다.

그 다음 줄에는 두 번째 스트라이커가 i번 점에서 첫 번째 스트라이커의 i+1번 점으로 패스를 할 때의 난이도 n-1개가 주어진다. 다음 줄에는 두 번째 스트라이커가 i번 점에서 i + 1 드리블 할 때의 난이도 n-1개가 주어진다.

모든 난이도는 1000보다 작거나 같은 음이 아닌 정수이다.

출력

각각의 테스트 케이스에 대해서, 골로 연결하는데 필요한 난이도의 최솟값을 출력한다.

 

<코드>

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

int dp[100001][2];
int pass[100001][2];
int dribble[100001][2];
int c, n, l1, l2, s1, s2;

int main()
{
	cin >> c;

	while (c--)
	{
		cin >> n >> l1 >> l2 >> s1 >> s2;

		for (int i = 1; i <= n - 1; i++)
			cin >> pass[i][0];
		for (int i = 1; i <= n - 1; i++)
			cin >> dribble[i][0] ;
		for (int i = 1; i <= n - 1; i++)
			cin >> pass[i][1];
		for (int i = 1; i <= n - 1; i++)
			cin >> dribble[i][1];

		dp[1][0] = l1;
		dp[1][1] = l2;

		for (int i = 2; i <= n; i++)
		{
			dp[i][0] = min(dp[i - 1][0] + dribble[i - 1][0], dp[i - 1][1] + pass[i - 1][1]);
			dp[i][1] = min(dp[i - 1][1] + dribble[i - 1][1], dp[i - 1][0] + pass[i - 1][0]);
		}

		cout << min(dp[n][0] + s1, dp[n][1] + s2) << '\n';

	}
}

 

풀이 방법

 

dp[i][0]의 의미는

스트라이커 1이 i-1번째에서 i번째로 드리블 해올 때와

스트라이커 2가 i-1번째에서 i번째로 스트라이커 1에게 패스할 때를 비교해서 더 작은 값을 저장

 

마찬가지로 

dp[i][1]의 의미는

스트라이커 2가 i-1번째에서 i번째로 드리블 해올 때와

스트라이커 1이 i-1번째에서 i번째로 스트라이커 2에게 패스할 때를 비교해서 더 작은 값을 저장

 

예제 입력 1을 예로 들자면 주어진 입력을 그림으로 나타냈을 시에 아래와 같은 그림이 나오게 된다.

즉, 시작점에서 롱패스를 한 뒤부터 슛을 하기까지 최소의 난이도로 골을 연결해야 하는데 입력 1의 경우는 아래와 같은 동선이 답이 된다.

 

 

 

 

www.acmicpc.net/problem/3976

3976번: 역습