글 읽기 - O(N) 풀이가 존재하므로 확장된 문제를 만들면 좋겠습니다.

pentagon03 2년 전 2

O(N) 풀이가 존재합니다.

N의 범위가 10^6으로 확장된 문제를 새로 만드는 것을 건의드립니다!

startlink 2년 전 0

만들어주세요

blou888 1년 전 0

하나 여쭤보고 싶은게 있습니다.

O(N) 으로 풀어보고 싶어 열심히 머리를 싸메는 중인데,

제가 생각한 방법은
2장 이하일 땐, 가장 큰 값을 가져갈 수 있도록 하였고,

그 이외엔 다음의 규칙을 따르도록 하였습니다.

a,b,c,d

라는 카드가 있을 때

a를 가져가면서 b라는 선택지가 생겼을 때 (내가 갖는 이득 +a, 내가 손해 보는 값 - max(b,d))

d를 가져가면서 c라는 선택지가 생겼을 때 (내가 갖는 이득 +c, 내가 손해 보는 값 -max(a,c))

이 둘 중 더 값이 큰 값을 가져 갈 수 있도록 하였습니다.

서로 카드는 한장씩 가져가는 게임이고, 서로 턴제이니, 각각 한 칸 앞의 상황만 고려해도 된다고 판단하였는데, 혹시 놓치고 있는 부분이 있을까요?

#pragma warning(disable:4996)
#include <iostream>
using namespace std;


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	freopen("1.inp", "r", stdin);

	int tc;
	cin >> tc;

	while (tc--) {
		int N;
		int arr[10003] = { 0, };
		cin >> N;
		
		for (int i = 0; i < N; i++) cin >> arr[i];

		int str = 0, end = N - 1, sum = 0;
		bool turn = true;

		while (str <= end) {
			int val;
			//한장만 있을 때
			if (str == end) {
				if (turn) {
					sum += arr[str];
				}
				str++;
			}//두장 있을 때, 더 큰거
			else if (str + 1 == end) {
				if (arr[str] > arr[end]) {
					val = arr[str++];
				}
				else {
					val = arr[end--];
				}
				if (turn) sum += val;
			}
			else {
				int l = 0, r = 0;
				l = arr[str] - max(arr[str + 1], arr[end]);
				r = arr[end] - max(arr[end - 1], arr[str]);
				if (l == r) {
					if (arr[str] > arr[end]) {
						val = arr[str++];
					}
					else val = arr[end--];
				}
				else if (l > r) {
					val = arr[str++];
				}
				else {
					val = arr[end--];
				}

				if (turn) sum += val;
			}

			turn = !turn;
		}
		cout << sum << "\n";
	}
}

startlink 11달 전 1

https://www.acmicpc.net/proble...

pentagon03 11달 전 0

감사합니다:)

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

문제

문제

출처

ICPC

O(N) 풀이가 존재하므로 확장된 문제를 만들면 좋겠습니다.

pentagon03 2년 전 2

startlink 2년 전 0

blou888 1년 전 0

startlink 11달 전 1

pentagon03 11달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말