[백준] 25212번 조각케이크 [C++]

https://www.acmicpc.net/problem/25212

25212번: 조각 케이크

---

문제 설명

 

---

접근 방법

조각 케이크의 갯수가 최대 10개기 떄문에 브루트포스 방식을 사용해 모든 경우의수를 찾아내도 자원소모가 크지 않다.

따라서 브루트포스 방식을 통해 각각 경우마다 케이크 조각들의 총 합이 101/100(1.01)을 넘어갈 경우에 더 탐색을 하지 않고, 총 값이 101/100 와 99/100 사이에 있다면 탐색을 하지 않고 결과값을 1 늘린다.

이러한 방식대로 모든 경우를 다 탐색하면 가능한 모든 경우를 찾을 수 있다.

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int result;
float arr[10];
bool flag[10];
void find(float sum, int val) {
	if (sum > 1.01)return; //조각들의 총 합이 101/100 보다 큰 경우
	else if (sum >= 0.99) {//조각들의 총 합이 101/100 이하,99/100 이상인 경우
		result++;
		return;
	}
	for (int i = val+1; i < n; i++) { //i=val+1이여야 순서가 바뀌는 경우가 없어진다.
		if (!flag[i]) {
			flag[i] = true;
			find(sum +  1/ arr[i]  , i);
			flag[i] = false;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++)cin >> arr[i];
	for (int i = 0; i < n; i++) {
		flag[i] = true;
		find(1 / arr[i], i);
	}
	cout << result;
}

---

이 문제를 대회에서 풀 때, 4번의 WA를 받았는데, 그 이유가 double이 아닌 float를 사용한 경우였다.

사실 float와 double의 차이점에 대해 애매하게 알고 있고, 평소 유니티를 이용한 개발을 할 때 정확성보다 메모리등의 이유로 float형태를 자주 써서 float를 쓰게 되었는데, double형태보다 낮은 정확도 떄문에 wrong answer를 받게 되었다.

이번 대회가 아니였으면 몰랐을 기본적인 사항을 알게 되어서 큰 수확이 아니였나 생각된다.

 

중간에 있는 탐색 과정은 N과M 문제를 참고하면 좋을 것 같다.

15649번: N과 M (1)