글 읽기 - 반례가 있을까요?

pjh612 3년 전 0

v라는 벡터에 구간들을 저장하고 vrank 에 구간의 개수와 해당 숫자를 저장했습니다.

럭키셋들은 먼저 vrank에 저장해주고 그다음에 구간의 개수들을 계산했습니다.

vrank에 추가하는 로직은 start와 end 사이에서 중간 부분이 제일 언럭키 구간이 많으므로 start와 end 양쪽에서 점점 중간으로 좁혀가면서 추가하는 방식으로 했습니다 (ex .start = 1, end = 10 일경우 2,9 -> 3,8 -> 4,7 -> 5,6)

이런식으로 개수를 세면서 가장 큰 럭키숫자 이하의 범위만 계산을 하고 출력 개수가 모자란다면 가장 큰 럭키숫자보다 큰 숫자들을 차례대로 출력하면서 부족한 개수를 추가하는 방식으로 했습니다.

이 코드에 어떤 문제점이있고 어떤 반례가있고 이 접근 방식보다 더 좋은 방식이 있으면 알려주시면 감사하겠습니다.

#include <iostream>
#include<algorithm>
#include<math.h>
#include<map>
#include<memory.h>
#include<vector>
#include<queue>
#include<stack>
#include<string>

using namespace std;

long long luckyset[51];
vector<pair<long long, long long>> vrank;//{구간의개수,해당 숫자}
vector<pair<long long ,pair<long long, long long>>> v;//{end-start,{start,end}}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	int L;
	int cnt = 0;
	cin >> L;
	for (int i = 0; i < L; i++)
	{
		cin >> luckyset[i];
		v.push_back({ 0,{luckyset[i],luckyset[i]} });
	}

	int N;
	cin >> N;
	sort(luckyset, luckyset + L);

	for (int i = 0; i < L; i++)//럭키숫자 먼저 vrank 에 추가
	{
		vrank.push_back({ 0,luckyset[i] });
		cnt++;
		if (cnt == N)
		{
			sort(vrank.begin(), vrank.end());
			for (unsigned int i = 0; i < vrank.size(); i++)
				cout << vrank[i].second << ' ';
			return 0;
		}
	}


	long long s = 1, end = 0;
	for (int i = 0; i < L; i++)//럭키숫자 사이사이의 구간을 추가해준다.
	{
		s = end;
		end = luckyset[i];
		v.push_back({ end - s,{s,end} });
	}

	sort(v.begin(), v.end());

	//for (int i = 0; i < v.size(); i++)//test
	//{
	//	cout << v[i].first << " "<<v[i].second.first << " " << v[i].second.second << '\n';
	//}
	//cout << '\n';

	for (unsigned int i = 0; i < v.size(); i++)
	{

		if (v[i].second.first == v[i].second.second)
		{
		/*	vrank.push_back({ 0,v[i].first });
			cnt++;
			if (cnt == N)
				break;*/
			continue;
		}
		else if (v[i].second.second - v[i].second.first == 2)
		{
			vrank.push_back({ 0,v[i].second.first + 1 });
			cnt++;
			if (cnt == N)
				break;
		}
		else {
			long long start = v[i].second.first;//럭키숫자 시작점
			long long end = v[i].second.second;//럭키숫자 끝점
			if ((end - start) % 2 == 0) {//end- start 짝수일경우
				for (long long i = start + 1; i < start + (end - start) / 2; i++)
				{

					vrank.push_back({ (i - start) * (end - i) - 1, i });		
					cnt++;
					if (cnt == N)
						break;
					vrank.push_back({ (i - start) * (end - i) - 1, end - (i - start) });
					cnt++;
					if (cnt == N)
						break;
				}
				if (cnt == N)
					break;
				long long  l = start + (end - start)/2;//end- start 짝수일경우 중간값 하나만 추가해준다.
				vrank.push_back({ (l - start) * (end - l) - 1, l });
				cnt++;
				if (cnt == N)
					break;
			}
			else {//홀수일 경우
				for (long long i = start + 1; i < start + 1 + (end - start) / 2; i++)
				{

					vrank.push_back({ (i - start) * (end - i) - 1, i });//중간값 까지만 구한다.		
					cnt++;
					if (cnt == N)
						break;
					vrank.push_back({ (i - start) * (end - i) - 1, end - (i- start) });
					cnt++;
					if (cnt == N)
						break;
				}
			}
		}
		if (cnt == N)
			break;
	}
	//cout << '\n';
	long long n = luckyset[L - 1] + 1;//럭키숫자의 가장 큰값보다 1큰것

	sort(vrank.begin(), vrank.end());
	//for (unsigned int i=0; i< vrank.size(); i++)//test
	//	cout <<vrank[i].first<<' '<<vrank[i].second << '\n';
	//cout << '\n';



	for (unsigned int i = 0; i <vrank.size(); i++)
		cout << vrank[i].second << ' ';

	
	while (cnt < N)//개수가 모자라면 채워줌
	{
		cout << n << " ";
		n++;
		cnt++;
	}
}

감사합니다 덕분에 해당 문제는 해결을 했는데요 ㅠㅠ 왜 틀렸습니다가 뜨는지 잘 모르겠네요.. xofyd99님이 주신 반례는 럭키 숫자를 먼저 벡터에 넣고 개수 카운트 해주고 , 그 후 각 럭키숫자의구간을 돌면서 언럭키 구간의 개수를 카운트해서 벡터에 넣는데 다른 럭키 숫자의 구간을 탐색하지 못해서 발생한 경우 였는데요 이것을 해결 하기 위해 모든 구간을 탐색해주지만 각 구간은 최대 100개를 가질 수 있다는 것으로 카운트가 100이면 다음 구간을 탐색하는 것으로 바꿨습니다. 그래도 틀렸습니다가 뜨는데 어떤 것이 문제 인지 찾을수가 없네요 ㅠ 구간의 개수를 구하는 방법이 잘못 됐을까요?

#include <iostream>
#include<algorithm>
#include<math.h>
#include<map>
#include<memory.h>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<limits.h>
using namespace std;

long long luckyset[51];
vector<pair<long long, long long>> vrank;//{구간의개수,해당 숫자}
vector<pair<long long, pair<long long, long long>>> v;//{end-start,{start,end}}

int main() {
   cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
   int L;
   int cnt = 0;
   cin >> L;
   for (int i = 0; i < L; i++)
   {
      cin >> luckyset[i];
      v.push_back({ 0,{luckyset[i],luckyset[i]} });
   }

   int N;
   cin >> N;
   sort(luckyset, luckyset + L);

   long long s = 1, end = 0;
   for (int i = 0; i < L; i++)//럭키숫자 사이사이의 구간을 추가해준다.
   {
      s = end;
      end = luckyset[i];
      v.push_back({ end - s,{s,end} });
   }
   sort(v.begin(), v.end());

   //for (int i = 0; i < v.size(); i++)//test
   //{
   //   cout << v[i].first << " "<<v[i].second.first << " " << v[i].second.second << '\n';
   //}
   //cout << '\n';

   for (unsigned int i = 0; i < v.size(); i++)
   {
      int cnt = 0;
      if (v[i].second.first == v[i].second.second)
      {
         if(v[i].second.first ==0)
            vrank.push_back({ 0,v[i].second.first+1 });
         else
            vrank.push_back({ 0,v[i].second.first });
            cnt++;
         if(cnt==100)
         continue;
      }
      else if (v[i].second.second - v[i].second.first == 2)
      {
         vrank.push_back({ 0,v[i].second.first + 1 });
         cnt++;
         if (cnt ==100)
            break;
      }
      else {
         long long start = v[i].second.first;//럭키숫자 시작점
         long long end = v[i].second.second;//럭키숫자 끝점
         if ((end - start) % 2 == 0) {//end- start 짝수일경우
            for (long long i = start + 1; i < start + (end - start) / 2; i++)
            {

               vrank.push_back({ (i - start) * (end - i) - 1, i });
               cnt++;
               if (cnt == 100)
                  break;
               vrank.push_back({ (i - start) * (end - i) - 1, end - (i - start) });
               cnt++;
               if (cnt == 100)
                  break;
            }
            if (cnt == 100)
               break;
            long long  l = start + (end - start) / 2;//end- start 짝수일경우 중간값 하나만 추가해준다.
            vrank.push_back({ (l - start) * (end - l) - 1, l });
            cnt++;
            if (cnt ==100)
               break;
         }
         else {//홀수일 경우
            for (long long i = start + 1; i < start + 1 + (end - start) / 2; i++)
            {
               vrank.push_back({ (i - start) * (end - i) - 1, i });//중간값 까지만 구한다.      
               cnt++;
               if (cnt ==100)
                  break;
               vrank.push_back({ (i - start) * (end - i) - 1, end - (i - start) });
               cnt++;
               if (cnt == 100)
                  break;
            }
         }
      }
      if (cnt == 100)
         break;
   }
   //cout << '\n';
   long long n = luckyset[L - 1] + 1;//럭키숫자의 가장 큰값보다 1큰것
   int size = vrank.size();
   
   //for (unsigned int i=0; i< vrank.size(); i++)//test
   //   cout <<vrank[i].first<<' '<<vrank[i].second << '\n';
   //cout << '\n';

   sort(vrank.begin(), vrank.end());

   if (size < N)//모자라면
   {
      for (unsigned int i = 0; i < vrank.size(); i++)
         cout << vrank[i].second << ' ';
      while (size < N)
      {
         size++;
         cout << n++ << " ";
      }
   }
   else//모자라지 않으면 
   {
      for (unsigned int i = 0; i < N; i++)
         cout << vrank[i].second << ' ';
   }

}

pjh612 3년 전 0

자체 해결입니다.

if(cnt ==100)

break;

하는 부분에서 논리적인 문제가 있었는데 저 부분을 수정해서 정답을 받았습니다.(실수라고 할만큼 사소한 문제 였습니다.)

xofyd99 3년 전 1

해결하셔서 다행이네요!

저도 조건 하나 잘못써서 골머리 싸매다가 겨우 해결했었어요 ㅠㅠ

늦었지만 제가 푼 방식 말씀드리면, 경우를 3가지로 나눠서 차례대로 넣어줬어요!

1. unlucky 구간이 0인 값들 넣기 : lucky set 값, lucky set 가운데에 끼어있는 값(lucky set이 1, 3 이면 2)

2. unlucky 구간이 0보다 크면서 유한한 값 넣기 : lucky set의 두 값 사이에 있는 값들

3. unlucky 구간이 무한한한 값 넣기 : lucky set의 최대 값보다 큰 값들

아마 1번 경우에 저와 다르게 구하셨던 것 같네요!

pjh612 3년 전 1

생각 공유해주셔서 감사합니다 ㅎㅎ. 제 코드는 많이 지저분하네요

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

문제

문제

출처

ICPC

반례가 있을까요?

pjh612 3년 전 0

xofyd99 3년 전 3

pjh612 3년 전 0

pjh612 3년 전 0

xofyd99 3년 전 1

pjh612 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말