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

원래 맥북에 관심이 크게 없었는데...

회사 개발환경이 Windows 호환이 잘 안되는 것들이 몇 개 있어서 맥북을 하나 사야하나 고민하게 됐다..

지금 맥북 프로가 있지만, 이전에 다니던 대학원 연구실꺼라 학교자산으로 잡혀서 반납해야한다.. ㅜ (지금은 내 맘대로 대여 중...ㅎㅎ)

 

맥북에 관심 없던 이유 중 하나는 일단 가격이 비싼게 컸고, 연구실 맥북(새 제품) 을 받아서 1년 조금 넘게 사용했을 때 부터 노트북 하판?이 수평이 안맞게 됐다. 아마 노트북연결해서 쓰고 했는데, 발열 때문에 하판이 늘어난 듯.. 

 

1년 남짓 썼는데 발열 때문에 하판이 늘어나서 달가닥 달가닥 거리니, 비싼 값을 못한다고 생각해서..

내 돈 주고 안사서 다행이다..? 라고 생각했었다 ㅋㅋㅋ

 

취업하면 데스크탑 하나 맞춰야지(게임해야되니까) 하고 있었는데,,  맥북부터 사야될 듯하다..

언제까지 졸업한 연구실 노트북 빌려쓰고 있을 순 없으니.....

 

ItSub 잇섭님 영상보니 이번 M1칩 탑재된 MacBook이 꽤 잘나온 것 같다. 반응속도도 빠르고. 발열도 적고.

내가 개발하는 것들이 인공지능쪽도 아니고, Restful API 만들고하는 정도다보니 MacBook Pro까지는 필요없을 것 같고, 

메모리 넉넉하게 Air 사면 딱 맞을 것 같다.

 

 

메모리 16GB로 변경하니 190만원.. 음

 

 

 

데스크탑은 언제 사지.. (그래픽카드 가격 좀 내려갔으면)

 

취업하고 돈을 벌어서 다행이긴한데,, 돈 쓸일이 많아서 앞으로 월급이 계좌를 스쳐 지나갈 것 같다...

 

'일상' 카테고리의 다른 글

2021' MacBook Air 살까 ?  (0) 2021.05.09

소프트웨어 개발자로서 도태되지 않고 성장할 수 있는 몇 가지 원칙을 정리한 글이 있어 퍼옵니다.

(원문: http://www.allofsoftware.net/2012/08/blog-post_6.html )

 

1. 관리와 개발 일을 분리하라.

 관리자가 될 것이 아니라면 관리 일은 아무리 열심히 해도 개발자 경력에 별 도움이 안된다. 하지만 회사의 사정상 싫어도 관리 일을 떠맡을 수 밖에 없는 경우가 있다. 그런 경우에도 본인의 정체성을 명확히 해야 한다. 개발과 관리 일을 섞어서 하지 말고 구분해야 한다. 즉, 자신이 하고 있는 일 중에서 어떤 일이 관리고 어떤 일이 개발인지를 구분해야 한다.

 개발이 주업이고 관리는 부업임을 명확히 해야 하고, 언제든지 관리 일은 버릴 수 있도록 준비를 해야 한다.

 

2. 경력과 수준에 맞는 일을 해라. 

 경력이 많아지면 그게 걸맞는 수준의 일들을 해야 한다. 경력이 늘어가도 똑같은 일을 그저 더 빠르고 능숙하게 하고 있다면 밥값을 못하고 있을 가능성이 높다. 그런 상태라면 개발자 경력을 오래 보장 받기는 어렵다. 결국 도태될 것이다.

경력이 늘어갈수록 누구나 할 수 있는 일들은 후배에게 물려 주어야 한다. 그리고는 설계, 분석 업무의 비중을 높이고 회사의 기술 전략에 신경을 써야 한다. 경력이 더욱 늘어갈수록 자신의 팀 뿐만 아니라 타팀, 더 나아가서 회사 전체의 프로젝트에 기여를 해야 한다.

 

 이를 위해 문서화는 필수다. 개발 내용이 문서로 적혀 있어야 서로 리뷰가 가능하고 타팀의 프로젝트도 검토를 해서 나의 전문지식을 불어 넣을 수가 있다.

 

3. 권력욕을 버려라.

 개발자로서 계속 나아가겠다고 결심을 했다면 어쨌든 권력욕은 버려야 한다. 권력을 얻기 위한 거의 모든 행동은 개발 일과는 거의 관계가 없다. 방해만 될 뿐이다. 개발자는 권력보다는 뛰어난 기술력에서 자연스럽게 나오는 파워를 가져야 한다. 

 

4. 끊임 없이 코딩하라.

 개발자는 30년을 일해도 감독, 코치가 아니라 선수다. 코딩에서 손을 놓으면 급속도로 개발자의 길과 멀어진다. 주변을 보면 관리나 좀 하고 코딩은 전혀 안하면서 여기저기 감 놔라 대추 놔라 훈수를 두는 무늬만 개발자가 매우 많다. 이들은 개발자가 아니고 개발자였을 때 쌓아 놓은 지식의 약발도 별로 오래 가지 않는다.

 

5. 새로운 기술을 익혀라.

 꾸준히 새로운 기술을 익혀야 한다. 시간이 흐를수록 점점 더 많은 새로운 기술들이 나오고 있다. 이를 따라잡기는 보통 어려운 일이 아니다. 적절하게 시간 투자를 해야 한다. 모든 기술을 다 마스터 할 필요는 없다. 나중에 필요할 때 언제든지 생각이 나게 하면 된다. 필요할 때 필요한 만큼 더 익히면 된다.

 

6. 소프트웨어 개발 전문가로 포지셔닝을 하라.

 경영자가 본인을 소프트웨어 전문가로 믿도록 하라. 경영자가 기술 전략을 같이 의논하게 하고 기술 관련된 정책을 제대로 수립할 수 있도록 보좌하라. 

 

7. 후배들의 롤모델이 되어라.

 선임 개발자가 어떤 식으로 일하는지 보여주고 기술력에서 오는 파워를 보여줘라. 이는 본인을 위해서도 더 일하기 좋은 개발환경을 만드는데 도움이 되는 일이다.

 

 

'도움이 되는 글' 카테고리의 다른 글

소프트웨어 개발자의 나아갈 길  (0) 2021.05.08

+ Recent posts