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

 

2529번: 부등호

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제

www.acmicpc.net

 

문제의 조건 

1. k 는 2보다 크거나 같고, 9보다 작거나 같다

2. k+1개의 숫자는 서로 다른 숫자이다

3. k개의 부등호에 맞는 값 중 최대값, 최소값을 구해야 한다

 

 

부등호에 '<=', '>=' 이 존재하고 서로 다른 숫자라는 조건이 없었다면, 경우의 수가 1e10 이 돼 TLE이 나겠지만, 

서로 다른 k+1 개의 수를 찾기 때문에 (k+1)! 의 경우의 수만 찾으면 된다.

 

처음에는 재귀함수를 통해 백트랙킹으로 풀었다.

 

소스코드 (백트랙킹)

숫자가 최대 10개이므로 비트마스크로 사용한 숫자를 체크하며, 조건이 맞지 않으면 재귀를 탈출하고, 

k+1 개의 숫자를 다 채우면 1을 리턴하면서 종료된다.

 

최솟값은 0부터 시작해서 찾아야하고, 최댓값은 9부터 시작해서 내려가며 찾아야하기 때문에

같은 재귀라도 반복문을 달리 사용해야하는 번거로움이 있었다.

 

  1. #include<stdio.h>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<string>
  5. using namespace std;
  6. typedef long long ll;
  7. int k;
  8. char karr[11];
  9. string min_="", max_="";
  10. bool inline chk(int a, char c, int b){
  11. return c == '>' ? a>b : a<b;
  12. }
  13. string num(vector<int>& ans){
  14. string s = "";
  15. for(int i=0; i < ans.size(); i++){
  16. s += ans[i] + '0';
  17. }
  18. return s;
  19. }
  20. int solve(vector<int>& ans, int visited, int p, int ismax){
  21. if(p == k) {
  22. return 1;
  23. }
  24. int cur = ans[p];
  25. int init = ismax ? 9 : 0;
  26. int iter = ismax ? -1 : 1;
  27. int end = ismax ? -1 : 10;
  28. for(int pp1=init; pp1 != end; pp1+=iter){
  29. if(visited & (1<<pp1))
  30. continue;
  31.  
  32. if(chk(cur, karr[p], pp1)){
  33. ans.push_back(pp1);
  34. if(solve(ans, visited | (1<<pp1), p+1, ismax))
  35. return 1;
  36. ans.pop_back();
  37. }
  38. }
  39. return 0;
  40. }
  41. string solve_(int i, int ismax){
  42. int visited = 0;
  43. vector<int>ans;
  44.  
  45. ans.push_back(i);
  46. visited |= (1<<i);
  47. if(solve(ans, visited, 0, ismax)){
  48. return num(ans);
  49. }
  50. return "";
  51. }
  52. int main(){
  53. scanf("%d", &k);
  54. for(int i=0;i<k;i++){
  55. scanf(" %c", &karr[i]);
  56. }
  57.  
  58. for(int i=0; i<10; i++){
  59. min_ = solve_(i, 0);
  60. if(min_ != "") break;
  61. }
  62.  
  63. for(int i=9; i>=0; i--){
  64. max_ = solve_(i, 1);
  65. if(max_ != "") break;
  66. }
  67. printf("%s\n%s\n", max_.c_str(), min_.c_str());
  68. return 0;
  69. }

 

 

풀다보니 최소값은 0~k 의 숫자, 최대값은 9~9-k 까지의 숫자만 사용하면 부등호를 만족하는 순서를 찾을 수 있기 때문에,

k 가 9인 경우 최대 10! 까지만 돌기 때문에 조합으로 풀 수 있겠다 생각됐다.

 

 

소스코드 (조합)

조합으로 푸니 코드가 깔끔해졌다.. 진작 이렇게 풀걸

처음부터 조합으로 풀 생각을 할 수 있도록 문제 해결 전략을 잘 세워야겠다..

 

  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<vector>
  4. using namespace std;
  5. int k;
  6. char karr[10];
  7. bool inline chk_(int a, char c, int b){
  8. return c == '>' ? a>b : a<b;
  9. }
  10. int chk(vector<int>& cand){
  11. for(int i=0; i<k; i++){
  12. if(!chk_(cand[i], karr[i], cand[i+1]))
  13. return 0;
  14. }
  15. return 1;
  16. }
  17. int main(){
  18. scanf("%d", &k);
  19. for(int i=0; i<k;i++)
  20. scanf(" %c", &karr[i]);
  21.  
  22. vector<int> min_ = vector<int>(k+1), max_ = vector<int>(k+1);
  23. for(int i=0; i<=k; i++){
  24. min_[i] = i;
  25. max_[i] = 9-i;
  26. }
  27.  
  28. do{
  29. if(chk(min_)) break;
  30. }while(next_permutation(min_.begin(), min_.end()));
  31.  
  32. do{
  33. if(chk(max_)) break;
  34. }while(prev_permutation(max_.begin(), max_.end()));
  35.  
  36. for(int i=0; i<=k; i++)
  37. printf("%d",max_[i]);
  38. printf("\n");
  39. for(int i=0; i<=k; i++)
  40. printf("%d",min_[i]);
  41. printf("\n");
  42. return 0;
  43. }

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24
BOJ 1305 광고  (0) 2020.09.24
BOJ 10826 피보나치 수 4  (0) 2020.09.04

+ Recent posts