글 읽기 - 어느 반례가 존재하는것인지 모르겠습니다 ㅜㅜ

nhchoi98 4년 전 1

제가 시도 해본 케이스는

1. 2000 2000 0

A가 모두 1000000 일때

출력: 2000000000

2. 2000 0 1000

B가 모두 1000000 일때

출력: 1000000000

3. 1 1 0

아무값 --> 입력한 대로 출력됨

4. 2 0 1

아무값 --> 입력한대로 출력됨

5. 2 2 0

1, 10

출력: 11

6. 5 5 5

1 2 3 4 5

10 20 30 40 50

출력:95

7. 6 6 6

1 2 3 4 5 6

10 20 30 40 50 60

출력: 150

과 예시로 주어진 테스트 케이스를 집어넣어 보았습니다.

전부 최대값으로 넣어주었을 때, 오버플로우가 나지 않는 범위임을 감안하면 어딘가 논리적으로 문제가 있다 생각합니다..

어떤 반례가 있을까요..?

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int get_sum_A(vector<int>& Pretty_A, int A)
{
	int result = 0;
	for (int i = 0; i < A; i++)
		result += Pretty_A[i];

	return result;
}

int get_sum_B(vector<int>& Pretty_B, int B)
{
	int result = 0;
	for (int i = 0; i < B; i++)
		result += Pretty_B[i];

	return result;
}



int main()
{
	int N, A, B; // N= 타일링을 해야하는 폭, A = 사용가능한 2*1 타일의 갯수, B= 사용가능한 2*2 타일의 갯수 
	int moduler, division;
	int maximum = 0; //예쁨값은 양수로 전부 입력되므로, 최대값은 0으로 초기화 한 후 여기에 저장됨 
	int temp;
	vector<int>Pretty_A; //2*1 타일의 예쁨값 저장 
	vector<int>Pretty_B; //2*2 타일의 예쁨값 저장 

	cin >> N >> A >> B;

	for (int i = 0; i < A; i++) { // 2*1 타일의 예쁨정도를 입력받음 
		int temp =0;
		cin >> temp;
		Pretty_A.push_back(temp);
	}
	
	sort(Pretty_A.begin(),Pretty_A.end(),greater<int>()); //예쁨값을 내림차순으로 정렬 

	for (int i = 0; i < B; i++) { //2*2 타일의 예쁨정도를 입력받음
		int temp = 0;
		cin >> temp;
		Pretty_B.push_back(temp);

	}
	sort(Pretty_B.begin(), Pretty_B.end(), greater<int>()); //예쁨값을 내림차순으로 정렬 

	division = N / 2;

	if (B > division) {  
		B = division;
		moduler = (N - (B * 2));
	}

	else
		moduler = (N - (B * 2));


	if (B != 0) {
		for (int i = B; i >= 0; i--) { //2*2타일은 최대 B개만 사용이 가능함 
			int j = moduler +((B - i) * 2); //2*2 타일 하나 빼면, 2*1 타일은 2개 들어감
			if (j <= A){
				temp = get_sum_A(Pretty_A, j) + get_sum_B(Pretty_B, i);
				if (temp > maximum)
					maximum = temp;
				
			}
		}
	}

	else if ((B * 2) == N)
		maximum = get_sum_B(Pretty_B, B); //전부 b인 경우 

	else
		maximum = get_sum_A(Pretty_A, A);// B가 0개인 경우
		
	cout << maximum << '\n';

	return 0;
}

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

문제

문제

출처

ICPC

어느 반례가 존재하는것인지 모르겠습니다 ㅜㅜ

nhchoi98 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말