14889. 스타트와 링크
사람은 총 N명, 최대 20명 이를 순열로 늘어 놓아서 앞에는 스타트팀, 뒤에는 링크팀으로 하면 중복계산도 상당히 많고, 총 경우의 수는 20! = 상당히 큰 수이다 >>>>>>>>>>>> 1억 당연히 시간초과가 난다. 문제를 풀면서 자연스럽게 생각할 수 있는 것은 사실 조합이다. 20C10 는 10! 보다 작을 것이라는 것을 예측할 수 있는데 실제로 그 결과는 10!(3백만)보다 훨씬 작다. 18만정도이다. 여기에 각 팀 스코어를 계산해야하는 시간이 (N/2) x (N/2) 이므로 100이라고 하면, 1800만 < 2초 안에 가능하다. 내가 맨 처음에 한 것은, 예를들어 1, 2, 3을 뽑았으면 총 1, 2, 3, 4, 5, 6 인 set에서 1, 2, 3을 뽑는 것이다. 즉 4, 5, 6을 만드는 것..
2019. 9. 21.
[백트래킹] 백준 2580 스도쿠
백트래킹을 알고 있다면, 그대로 하면 풀린다! 원리는 간단하다, 모든 경우를 탐색하는 것인데 빈칸에 들어갈 수 있는 후보자를 찾은 뒤, 처음 후보자를 놓고, 다음 빈칸을 같은 방법으로 탐색한다. 그러다가 막히면(후보자가 없다거나) 다시 돌아오면 된다 (백트래킹!) 주의할 것은, 스페셜 져지문제인 만큼 답이되는 후보 제일 먼저 발견한 것을 찾으면, 바로 프로그램을 종료하면 된다. 헤더파일에 있는 exit(0)함수를 썼다. 후보자를 찾기 위해 가로세로를 탐색하고, 사각형을 탐색하는데 아이디어만 잘 내면 될 듯하다! #include #include #include #include using namespace std; int N = 9; int a[9][9]; int dx[] = {-1, 1, 0, 0}; in..
2019. 9. 19.
[백트래킹] 1987 알파벳
1. 알파벳 보드 b 생성 2. 알파벳 모음 alphabets 생성 - 이미 찾은 알파벳 확인용 3. 방향 설정 상 하 좌 우 dx = {-1, 1, 0, 0} dy = {0, 0, -1, 1} 이 보드의 (0, 0) 부터 시작해서, 상하좌우 매번 탐색하면서 - 보드의 바깥으로 가는 경우는 다시 돌아옴(백트랙). - 새로운 알파벳을 탐색했으면 기록하고, 다음 경로 탐색. - 이미 기록된 알파벳을 탐색했으면 백트랙. ex) 2 4 CAAB ADCB 이와 같은 알파벳 보드에서, 재귀함수가 어떻게 진행되는지 보자. C : 알파벳 체크. 1 상 : 없음, 돌아옴 2 하 : A 체크 2-1 상 : C가 이미 체크 되어있음, 돌아옴 2-2 하 : 없음, 돌아옴 2-3 좌 : 없음, 돌아옴 2-4 우 : D 체크 2..
2019. 6. 27.
