글 읽기 - 반례를 못찾겠습니다 ㅠ,ㅠ

smiley_bin 4년 전 0

반례를 못찾겠습니다 ㅠ,ㅠ 제일 작은 수를 찾은 뒤에 바꾸는게 확률의 최대치라고 생각해서 구현했는데, test case가 1개인 지라 몇개의 test case를 만들어서 해본 결과도

다 잘 나오는데 틀리네요 ㅠ,ㅠ

#include<iostream>
#include<queue>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;

int N;
int visit[20];

int main() {
	vector<unsigned long long> result;
	vector<int> r_visit[1000];

	cin >> N;

	for (int i = 0;i < N;i++) {
		memset(visit, 0, sizeof(visit));
		int num1, num2, num3; //num1 주사위 개수, num2 최소 충족값 , num3 주사위 값   
		cin >> num1 >> num2; 
		vector<pair<int, int>> dice;
		int sum = 0;
		for (int j = 0;j < num1;j++) {
			cin >> num3;
			dice.push_back({ num3,j });
			sum += num3;
		}

		float percent = 1;
		unsigned long long r_value = 0;

		while (1) {
			sort(dice.begin(), dice.end());
			visit[dice[0].second] = 1;

			if (sum >= num2) { //조건을 만족하는 경우 
				for (int l = 0;l < num1;l++) {
					r_visit[i].push_back(visit[l]);
				}
				r_value = pow(6, num1)*percent;
				result.push_back(r_value);
				break;
			}
			else {
				int idx = 0;
				int cnt = 1;
				int per_cnt = 0;
				int tmp_sum;
				int flag = 0;

				while (1) {
					visit[dice[idx].second] = 1; //만족을 못할시에 오름차순 정렬을 했기 때문에 제일 작은 값을 키워본다
					tmp_sum = sum - dice[idx].first;
					cnt++;
					tmp_sum += cnt;
					if (tmp_sum >= num2) { //조건보다 크거나 같으면 경우의 수 증가
						per_cnt++;
					}
					if (cnt == 6) { //끝까지 올라갔을 때 
						if (tmp_sum < num2) { //더한 값이 조건에 안맞는다면
							flag = 1;
							percent = 1.0 / 6.0; //무조건 6이 나와야 하니까 1/6으로 고정후
							sum -= dice[idx].first;
							dice[idx].first = 6; //sum 바꿔준다.
							per_cnt = 0;
							cnt = 0;
							idx++;
							sum += 6;
						}
						else {
							if (flag == 0) { //한번 다시 던졌는데 성공한 경우
								percent = per_cnt / 6.0;
								sum = num2;
								break;
							}
							else {//한번 다시 던졌는데 실패해서 그이상으로 다시 던지는 경우
								percent = percent*(per_cnt / 6.0);
								sum = num2;
								break;
							}
						}
					}
				}
			}
		}
	}

	for (int i = 0;i < N;i++){
		cout << result[i] << "\n";
		for (int j = 0;j < r_visit[i].size();j++) {
			cout << r_visit[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}

jh05013 4년 전 0

1
1 6
6

을 넣으면 출력의 두 번째 줄이 잘못 나옵니다.

smiley_bin 4년 전 0

이렇게 나오거나

이렇게 나오면 되지않나요?!?

jh05013 4년 전 0

주사위를 굴리면 안 되기 때문에 6 0이 나와야 합니다. 이 코드는 6 1을 출력합니다.

smiley_bin 4년 전 0

죄송하지만 예제샘플에서 마지막 예제가

2 5 4 라서 총합이 11이라 8을 넘는데 출력을

1 0 0으로 하길래 저도 디폴트를 1로 해놔서 출력이 저렇게 나오는데 같은 경우가 아닌가요?ㅠㅠ

jh05013 4년 전 1

3 8 \n 2 5 4에서는 첫 번째 주사위를 굴리든 말든 상관이 없습니다. 첫 번째 주사위를 굴려서 무슨 값이 나오더라도 합은 무조건 8 이상이 되기 때문입니다. 그래서 0 0 0을 출력해도 되고 1 0 0을 출력해도 됩니다.

하지만 1 6 \n 6에서는 첫 번째 주사위를 굴리면 안 됩니다. 굴려서 다시 6이 나오지 않는 이상 합이 6 이상이 되지 않기 때문입니다.

smiley_bin 4년 전 0

좋은 답변 감사합니다! 코드를 바꿔서 테스트 케이스를 몇 개 넣어보고 했는데 제 결과론 맞게 나오는데, 실패가 나오는 것을 봐서는 코드를 DP 방법으로 다시 풀어보는게 현명한 것 같습니다 ㅠ,ㅠ

밑 방법처럼 시뮬레이션(?) 처럼 푸니까 반례가 생각외로 많이 나오는 모양입니다! 감사합니다:>

#include<iostream>
#include<queue>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;

int N;
int visit[20];

int main() {
	vector<unsigned long long> result;
	vector<int> r_visit[1000];

	cin >> N;

	for (int i = 0;i < N;i++) {
		memset(visit, 0, sizeof(visit));
		int num1, num2, num3; //num1 주사위 개수, num2 최소 충족값 , num3 주사위 값   
		cin >> num1 >> num2; 
		vector<pair<int, int>> dice;
		int sum = 0;
		for (int j = 0;j < num1;j++) {
			cin >> num3;
			dice.push_back({ num3,j });
			sum += num3;
		}

		float percent = 1;
		unsigned long long r_value = 0;

		while (1) {
			sort(dice.begin(), dice.end());

			if (sum >= num2) {
				for (int l = 0;l < num1;l++) {
					r_visit[i].push_back(visit[l]);
				}
				r_value = pow(6, num1)*percent;
				result.push_back(r_value);
				break;
			}
			else {
				int idx = 0;
				int cnt = 1;
				int per_cnt = 0;
				int tmp_sum;
				int flag = 0;

				while (1) {
					visit[dice[idx].second] = 1;
					tmp_sum = sum - dice[idx].first;
					cnt++;
					tmp_sum += cnt;
					if (tmp_sum >= num2) {
						per_cnt++;
					}
					if (cnt == 6) {
						if (tmp_sum < num2) {
							flag++;
							percent = 1.0 /(pow(6.0,flag));
							sum -= dice[idx].first;
							dice[idx].first = 6;
							per_cnt = 0;
							cnt = 0;
							idx++;
							sum += 6;
						}
						else {
							if (flag == 0) {
								percent = per_cnt / 6.0;
								sum = num2;
								break;
							}
							else {
								percent = percent*(per_cnt / 6.0);
								sum = num2;
								break;
							}
						}
					}
				}
			}
		}
	}

	for (int i = 0;i < N;i++){
		cout << result[i] << "\n";
		for (int j = 0;j < r_visit[i].size();j++) {
			cout << r_visit[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다 ㅠ,ㅠ

smiley_bin 4년 전 0

jh05013 4년 전 0

smiley_bin 4년 전 0

jh05013 4년 전 0

smiley_bin 4년 전 0

jh05013 4년 전 1

smiley_bin 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말