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.
14888. 연산자 끼워넣기
같은 것을 포함한 순열이라는 느낌을 받고, 이를 구현해보려고 하다가, 잘 안되서 결국 못했다. 조합을 여러번 하는 것으로 구현해보려고 하다가, 너무 복잡해지는 감이있어서, 다시 완전탐색을 시도. 연산자는 최대 10개이고, 같은 연산자라도 다 다르다고 취급하고, 순열의 수를 생각해봤을 때, O(N!)의 시간복잡도를 가진다. 10! = 3,628,800 이므로 충분. 처음에는, 마지막 기저조건(return)에서 모든 결과값을 계산하는데 O(N)시간을 써먹어서 시간이 좀 느리게 나왔다. #include int N; int nums[12]; char opers[12]; int chk = 1
2019. 9. 19.
[백트래킹] 백준 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.
