3-M 질문

Question

http://boj.kr/51928d5f470e44a0839c4bfd433f3e08 arr이라는 배열을 만들어서 부등호랑 입력받을 문자들을 arr한곳에 다 넣어놓고 이것을 그래프로 생각을 한뒤 DFS로 완탐해서 풀었는데 답은 항상 나오는데 어디에 예외 사항이 있는지 모르겠습니다. 제가 직접 숫잘 넣어보면서 봐도 답은 잘 나오는데 계속 틀렸다고 뜨는데 어느 부분이 잘못된 것일까요? 숫자는 항상 입력받은 k개 길이만큼만 다 걸러낸다음에 arr의 k * 2인덱스 에 숫자가 있는 경우 == k개 만큼 숫자를 다 채웠을 경우 최대최소를 구할 수 있도록 하였습니다.

큰돌 · Answer

안녕하세요 stark님 ㅎㅎ 이 코드를 봤을 때 로직상은 괜찮은 거 같아요. 반례 어느정도 넣어봤는데 다 통과되네요.. 다만 걸리는게 좀 있는데요. 이부분이요. arr[NextPos] 같은 경우 해당 NextNum으로 했다가 "초기화"로 0이란 값을 넣고 있는데 0은 우리가 넣을 수 있는 값의 후보군이 아닌가요? 즉 -1 또는 0 ~ 9에서 포함되지 않은 수로 해야 되지 않을까요? number[NextNum] = 1; visited[NextPos] = 1; arr[NextPos] = NextNum; Go(NextPos, NextNum); number[NextNum] = 0; visited[NextPos] = 0; arr[NextPos] = 0; 그리고 코드를 좀 다듬을 필요가 있는데요. 코드 상 불필요한 코드가 있는데요. 여기서 v에 굳이 할당할 필요가 있나요? bool CheckNum(int num) { int v = number[num]; if (v != 0) return false; return true; } 이거는 curPos가 아니라 curValue가 맞는 표현이겠죠? bool Cango(int curPos, int nextPos, int num) 중첩for문을 쓸 때는 i >> i 이렇게 하지 말아주세요. 지금 이 코드는 괜찮지만, 나중에 헷갈려서 틀릴 수도 있어요. :) for (int i = 0; i < 10; ++i) { int num = i; visited[0] = 1; number[num] = 1; arr[0] = num; Go(0, num); memset(visited, 0, sizeof(visited)); memset(number, 0, sizeof(number)); for (int i = 0; i < k * 2; i += 2) { arr[i] = 0; } } 하지만 나머지 부분 최소, 최대의 초기값 부분, L, G로 할당한 부분, 배열의 적절한 크기, 로직의 구성 모두 다 잘 짜셨습니다. 감사합니다.