글 읽기 - 14739번 질문 있습니다.

snrnsidy 5년 전 0

다름이 아니고 아무리 생각을 해도 문제가 풀리지 않아서 질문을 드립니다...

arr1 : 현재의 인덱스로부터 증가하거나 유지되는 수열이 끝나는 위치를 저장해둔 배열
arr2 : 현재의 인덱스로부터 감소하는 수열이 끝나는 위치를 저장해둔 배열

arr1,arr2를 이용해서 각 부분배열의 시작위치(idx)로부터 최소의 나쁜 원소의 개수를 구해서 더하는 식으로 구현을 했습니다.
나쁜 원소의 개수를 구하는 방법은 부분배열의 길이 - arr1[idx] (부분배열의 길이 > arr1[idx]) , 부분배열의 길이 - arr2[idx] (부분배열의 길이 > arr2[idx]) 중에서 최소가 되는 개수를 가지고 구했습니다.
이런식으로 코딩했는데 틀렸습니다가 나오네요.
혹시 로직이 잘못된걸까요? 생각을 해도 모르겠어요ㅠㅠ 힌트라도 주시면 감사하겠습니다ㅠㅠ

#include <bits/stdc++.h>

using namespace std;

int arr1[100001]={-1,};
int arr2[100001]={-1,};

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n,t;
	vector <int> v;

	cin >> n;

	for(int i=0;i<n;i++)
	{
		cin >> t;
		v.push_back(t);
	}

	memset(arr1,-1,sizeof(arr1));
	memset(arr2,-1,sizeof(arr2));


	int start = 0;

	for(int i=1;i<n;i++)
	{
		if(v[i]<v[i-1])
		{
			arr1[start] = i;
			start = i;
		}
	}
	arr1[start] = n;


	start = 0;

	for(int i=1;i<n;i++)
	{
		if(v[i]>=v[i-1])
		{
			arr2[start] = i;
			start = i;
		}
	}
	arr2[start] = n;

	int x = arr1[0];
	for(int i=1;i<n;i++)
	{
		if(arr1[i]==-1)
		{
			arr1[i] = x;
		}
		else
		{
			x = arr1[i];
		}
	}	

	x = arr2[0];
	for(int i=1;i<n;i++)
	{
		if(arr2[i]==-1)
		{
			arr2[i] = x;
		}
		else
		{
			x = arr2[i];
		}
	}
	/*
	for(int i=0;i<n;i++)
	{
		cout << arr1[i] << ' ';
	}
	cout << '\n';
	for(int i=0;i<n;i++)
	{
		cout << arr2[i] << ' ';
	}
	cout << '\n';	
	*/
	int q;
	cin >> q;
	for(int i=0;i<q;i++)
	{
		cin >> t;

		int cnt = 0;
		int res = 0;
		int idx = 0;
		while(1)
		{
			if(idx>=n)
			{
				break;
			}
			cnt++;
			int x = 0,y = 0;
			int d = min(cnt*t,n);
			if(d>arr1[idx])
			{
				x = d - arr1[idx];
			}
			if(d>arr2[idx])
			{
				y = d - arr2[idx];
			}
			res += min(x,y);
			idx+=t;
		}
		cout << cnt << ' ' << res << '\n';
	}
	return 0;
}

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

문제

문제

출처

ICPC

14739번 질문 있습니다.

snrnsidy 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말