# [Platinum IV] 수열 찾기 [문제 링크](https://www.acmicpc.net/problem/14208) ## 문제 설명 <p>총 N개의 양의 정수로 이루어진 수열 B = B₀, ..., B_N-1가 주어진다. 이때, 아래와 같은 성질을 만족하는 수열 A = A₀, ..., A_N-1을 만들려고 한다.</p> <ul> <li>수열 A의 모든 수는 서로 달라야 한다.</li> <li>모든 A_i는 1보다 커야 한다.</li> <li>모든 i에 대해서, A_i^B_i (A_i의 B_i제곱)은 P_i로 나누어 떨어져야 한다. 이때, P_i는 A에서 A_i를 제외한 수를 모두 곱한 값이다. 즉, P_i = A₀×A₁×...×A_i-1×A_i+1×...×A_N-1 이다.</li> </ul> <p>수열 A를 만들 수 있는지 없는지 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 수열의 크기 N (2 ≤ N ≤ 50)이 주어진다. 둘째 줄에는 수열 B가 주어진다. (1 ≤ B_i ≤ 10)</p> ## 출력 <p>첫째 줄에 수열 A를 만들 수 있으면 1을 없으면 0을 출력한다.</p> ## 풀이 모든 $A_i$를 $2^k$ 꼴로 나타내면 지수만 신경쓰면 된다. $A_i$의 지수를 $a_i$라 하면, $a_i \cdot B_i \ge \sum\limits_{j \ne i} a_j$ 식이 나온다. 그 뒤 아래 식으로 정리된다. $a_i(B_i + 1) \ge \sum a_j$ $a_i(B_i + 1) \ge Sum$ $a_i \ge \frac{Sum}{B_i + 1}$ $\sum a_i \ge \sum \frac{Sum}{B_i + 1}$ $Sum \ge \sum \frac{Sum}{B_i + 1}$ $1 \ge \sum \frac{1}{B_i + 1}$ 이 때, $1 \gt \sum \frac{1}{B_i + 1}$인 경우에 대해선 항상 만들 수 있다. 하지만 $1 = \sum \frac{1}{B_i + 1}$는 모든 $a_i$에 대해 $a_i = \frac{Sum}{B_i + 1}$가 성립되기 때문에 $B_i$가 하나라도 같은 경우 중복된 $a_i$가 발생해 불가능하다. ``` c++ #include<bits/stdc++.h> using namespace std; int appear[11]; int fact11 = 11 * 9 * 8 * 7 * 5; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int total=0; for(int i=0;i<n;i++) { int b; cin >> b; total += fact11/(b+1); appear[b]++; } if(total==fact11) { for(int i=1;i<=10;i++) { if(appear[i]>1) { cout << 0; return 0; } } cout << 1; } else if(total<fact11) { cout << 1; } else { cout << 0; } } ```