글 읽기 - [14501]C++ next_permutation 사용하여 brute force

jhim000 4년 전 0

안녕하세요.

문제 풀다가 로직은 맞는 것 같은데, 이유를 찾지 못하여 질문 드립니다.

어떤 부분이 문제인지 알려주신다면 감사하겠습니다.

전체적인 로직은 다음과 같습니다.

N 줄에 주어지는 T, P를 큐에 저장
일을 받은 날까지 포함하여 큐에 담습니다. q.push_back({ i + 1, T, P });
총 N일 중에 일하는 날 수를 count 라는 변수를 만들어서 count가 1부터 N까지 증가하도록 합니다. (count = 일하는 날 수)
해당 count에서 일어날 수 있는 모든 경우의 수에 대하여 총 페이 (ans += cur.p)를 구합니다. 예를들어 전체 3일 중에 일하는 날 수 (count)가 2이면, (0, 1, 1), (1, 0, 1), (1, 1, 0) 이런 경우의 수가 도출되는데, 각 경우마다 총 페이의 최대 값을 pay라는 vector에 저장 합니다.
마지막으로 pay (vector)를 sort 하여 맨 뒤에 있는 값을 출력하도록 프로그래밍 하였습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
struct sangdam {
	int day, t, p; // day: 일을 받은 날, t: 소요되는 일 수, p: 상담 완료 후 받는 보수
};
deque<sangdam> q;
vector<int> pay; // 결과 값 나열 --> 마지막에 sort
int N;
int main(void) {
	cin >> N;
	for (int i = 0, T, P; i < N; i++) {
		cin >> T >> P;
		q.push_back({ i + 1, T, P }); // i가 N-1이면 마지막 날
	}
	// 1~N일 중에 어떤 날 일할지 정해서 1 채워넣기
	int count = 1; // 일하는 날 수
	while (count <= N) {
		int *permutation = new int[N];
		for (int i = 0; i < N - count; i++)	permutation[i] = 0;
		for (int i = N - count; i < N; i++)	permutation[i] = 1;
		int result = -1;
		do {
			int ans = 0;
			deque<sangdam> work;
			for (int i = 0; i < N; i++) {
				if (permutation[i] == 1)	work.push_back(q[i]);
			}
			while (!work.empty()) {
				sangdam cur = work.front(); work.pop_front();
				if (N - cur.day + 1 >= cur.t)	ans += cur.p;
			}
			result = max(result, ans); 
		} while (next_permutation(permutation, permutation + N));
		pay.push_back(result); // 각 날 중에 최대 result를 pay에 저장
		count++;
	}
	sort(pay.begin(), pay.end()); // 가장 큰 값 맨 뒤로
	cout << pay.back(); // 맨 뒤 반환
	return 0;
}

ha_ram 4년 전 0

로직이 틀렸습니다. 일하는 기간에는 다른 일을 못합니다.

위의 로직대로 작동하면 퇴사하기 전에 끝나는 모든 일을 다 해서 pay를 더한것밖에 안됩니다.

문제에서 주어진 조건인 " 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다. " 를 잘 생각해 보시기 바랍니다.

jhim000 4년 전 0

감사합니다.

접근 방식이 완전 틀린 것 같습니다.

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

문제

문제

출처

ICPC

[14501]C++ next_permutation 사용하여 brute force

jhim000 4년 전 0

ha_ram 4년 전 0

jhim000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말