글 읽기 - 왜 틀렸는지 모르겠어요 ㅠㅠ

woong611 6년 전 0

계속 틀렸다고 나오는데 어떤 경우에 안되는지 잘 모르겠어요 ㅠㅠ

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


int T;
int n;
int map[3][100001];
int dp[100001];
int check[100001];

vector<int> v;
int main() {
	int temp;
	cin >> T;

	while (T--) {
		cin >> n;

		for (int i = 1; i <= 2; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> temp;
				map[i][j] = temp;
			}
		}
		
		if (map[1][1] < map[2][1]) {
			check[1] = 2;
			dp[1] = map[2][1];
		}
		else if (map[1][1] > map[2][1]) {
			check[1] = 1;
			dp[1] = map[1][1];
		}
		else {
			dp[1] = map[1][1];
			check[1] = 0;
		}

		if(n >= 2){
		
		if (map[1][1] + map[2][2] < map[2][1] + map[1][2]) {
			dp[2] = map[2][1] + map[1][2];
			check[2] = 1;
		}
		else if (map[1][1] + map[2][2] > map[2][1] + map[1][2]) {
			dp[2] = map[1][1] + map[2][2];
			check[2] = 2;
		}
		else {
			check[2] = 0;
			dp[2] = map[1][1] + map[2][2];
		}


		for (int i = 3; i <= n; i++) {
			if (check[i - 2] == 1) {
				if (map[1][i] + map[2][i - 1] > map[2][i]) {
					dp[i] = dp[i - 2] + map[1][i] + map[2][i - 1];
					check[i] = 1;
				}
				else if (map[1][i] + map[2][i - 1] < map[2][i]) {
					dp[i] = dp[i - 2] + map[2][i];
					check[i] = 2;
				}
			}
			else if (check[i - 2] == 2) {

				if (map[1][i - 1] + map[2][i] > map[1][i]) {
					dp[i] = dp[i - 2] + map[1][i - 1] + map[2][i];
					check[i] = 2;
				}
				else if (map[1][i - 1] + map[2][i] < map[1][i]) {
					dp[i] = dp[i - 2] + map[1][i];
					check[i] = 1;
				}
			}
			else{
				
				if (map[1][i - 1] + map[2][i] > map[2][i - 1] + map[1][i]) {
					dp[i] = dp[i - 2] + map[1][i - 1] + map[2][i];
					check[i] = 2;
				}
				else if (map[1][i - 1] + map[2][i] < map[2][i - 1] + map[1][i]) {
					dp[i] = dp[i - 2] + map[2][i - 1] + map[1][i];
					check[i] = 1;
				}
				else
				{
					dp[i] = dp[i - 2] + map[2][i - 1] + map[1][i];
					check[i] = 0;
				}

				
			}
		}
}


		v.push_back(dp[n]);
}


	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << endl;
	}

	return 0;
}

gaelim 6년 전 0

2차원 dp를 이용하여

모든 경우의수를 고려해보아야 합니다.

지금은 1차원 dp를 이용하여 greedy 비슷하게 접근하신것같습니다...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 틀렸는지 모르겠어요 ㅠㅠ

woong611 6년 전 0

gaelim 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말