티스토리 뷰
[2529] 부등호
부등호 n개의 배열이 주어지면,
해당 부등호 들을 만족시키는 숫자 n+1개의 배열 중 가장 작은 숫자 배열과 가장 큰 숫자배열을 찾는 문제.
부등호 배열 A = {<, >} 가 주어지면 이를 만족하는 숫자는 0 < 2 > 1 , 1 < 3 > 2 , 2 < 4 > 3, ... , 8 < 9 > 7 과 같다.
이 중 가장 큰 숫자 배열은 897이고, 가장 작은 숫자배열은 021이다.
1) 그냥 다 보기
부등호가 기껏해봐야 9개가 주어지고, 10개의 숫자로 이루어진 배열이므로 최대 10!의 경우를 모두 보면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include <iostream> #include <algorithm> using namespace std; int main(){ int k; cin >> k; string h, l, a, ms, mns; long long mx = 0, mn = 9876543210; for(int i = 0; i < k+1; i++){ h.push_back('9'-k+i); l.push_back('0'+i); } for(int i = 0; i < k; i++){ char ch; cin >> skipws>> ch; a.push_back(ch); } do{ bool flg = true; for(int i = 0; i < a.size(); i++){ if(a[i] == '<'){ if(h[i] > h[i+1]) flg = false; }else{ if(h[i] < h[i+1]) flg = false; } } if(flg){ long long tmpmx = stoll(h), tmpmn = stoll(l); if(mx < tmpmx) { mx = tmpmx; ms = h; } if(mn > tmpmn) { mn = tmpmn; mns = l; } } }while(next_permutation(h.begin(), h.end()) & next_permutation(l.begin(), l.end())); cout << ms << endl; cout << mns << endl; return 0; } | cs |
당연히 시간은 고정적으로 걸리고, 10!의 경우를 모두 다 보는 만큼 걸린다.
2) 좀 더 효율적으로 풀어보자
재귀 적으로 경우의 수를 모두 다 보는 방식으로 바꾸면 훨씬 짧은 시간안에 해결할 수 있다.
작은 숫자의 배열을 찾는 경우 0부터 9까지 넣는 방식으로, 큰 숫자의 배열을 찾는 경우 9부터 0까지 넣는 방식으로 함수를 짜 넣으면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <cstdio> bool eq[10], set[10], finished; int a[10], k; bool isInRule(int idx, int n){ if(idx == 0) return true; else if(eq[idx-1]) return a[idx-1] < n; else return a[idx-1] > n; } int findAns(int idx, int remain, bool inv){ if(remain <= 0){ for(int i = 0; i <= k; i++) printf("%d",a[i]); printf("\n"); finished = true; return 0; } if(!inv){ for(int i = 9; i >= 0; i--){ if(isInRule(idx, i) && !set[i]){ a[idx] = i; set[i] = true; findAns(idx+1, remain-1, inv); if(finished) return 0; set[i] = false; } } } else { for(int i = 0; i < 10; i++){ if(isInRule(idx, i) && !set[i]){ a[idx] = i; set[i] = true; findAns(idx+1, remain-1, inv); if(finished) return 0; set[i] = false; } } } return 0; } int main(){ char ch; scanf("%d",&k); for(int i = 0; i < k; i++){ scanf(" %c",&ch); if(ch == '<') eq[i] = true; else eq[i] = false; } findAns(0, k+1, false); for(int i = 0; i < 10; i++) set[i] = false; finished = false; findAns(0, k+1, true); return 0; } | cs |
'Problem & Solving > Beakjoon judge' 카테고리의 다른 글
[2565] 전깃줄 (0) | 2019.09.25 |
---|---|
[2418] 단어 격자 (0) | 2018.09.20 |
[5397] 키로거 (0) | 2018.04.14 |
[1072] 게임 (0) | 2018.03.23 |
[2011] 암호코드 (0) | 2018.03.11 |
댓글