13460 구슬 탈출 2
삼성 SW 역량 문제. 방향이 4방향이니까, 한 방향에 대해서 깊히 생각해보고 구현하면 나머지는 비슷한 방법이다. 그래서 코드도 비슷하지만, 길어진 코드가 되었다. 총평 - 모든 경우의 수를 세는 dfs는 잘 구현했다. - dfs 기저조건에서, 최솟값을 구하는 방법을 이제는 낯설어 하지 말자. - 결국, 시뮬레이션의 디테일한 구성사항을 논리적 오류없이 구현해야하는 것이 중요했다. - 반례들을 몇 십 차례 적용해 본 결과로 논리적 허점을 찾고, 수정하여 답을 얻었다. - 문제였던 곳은, 빨간공과 파란공이 같은 선 상에 있을 때, 움직인 후 겹치지 않게 처리하는 부분이었다. 이 부분을 알고리즘 처음 짤 때부터, 신중히 생각하고 만들었으면, 더 좋았을 것 같다. #include int N, M; char a[..
2019. 10. 6.
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.
[SW Expert Academy] 1767. 프로세서 연결하기
DFS를 이용하지만, 조건이 덧붙여져있어서, return 되는 상황을 잘 생각해야하는 문제이다. 1) 전선이 연결된 코어 수는 최대가 되어야 하고, 2) 그 다음으로는, 전선 길이의 합이 최소가 되는 답을 찾으면 된다. 사실 이게 핵심이고, 나머지는 DFS이다. #include #include #include #include using namespace std; int N; int map_[12][12]; bool visited[12][12]; int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}; vector cores; int core_num; int line_ans; void go(int startidx, int line_len, int core_cnt){ if (st..
2019. 9. 18.
