c++2 경주로 건설 - 카카오 2020 C++ DFS 코딩테스트 풀이 다들 BFS풀고 공식해설도 BFS로 풀었다. BFS로 풀든 DFS로 풀든 상관 없지만 핵심은 완전탐색 과 메모이제이션 이 있어야 시간초과가 나지 않고 정답을 맞출수있다. 완전탐색이라는 방향에서 BFS나 DFS어느것으로 풀어도되는데 많은 블로그에서 DFS로 풀면 틀린다는 듯이 말을 해서 풀이를 올리게 되었다. 충분히 짧은 시간내에 정답이 가능하다. 핵심은 cost배열(메모이제이션) 에 최소비용을 계속 갱신해주고 이 최소비용보다 높다면 그 지점으로 이어지는 경로자체를 return시키는 것이다. #include #include #include int dr[4]={0,1,0,-1}; int dc[4]={1,0,-1,0}; int visited[30][30]={0,}; int cost[30][30]={0,}; u.. 2020. 9. 11. 보석 쇼핑 [카카오 2020 인턴 코딩테스트] C++ 투포인터 간단 명확 풀이 전형적인 투포인터 문제이다. 다음과 같이 for(int i=0;igems.size()) break; } 배열의 범위가 최대 10만 이므로 브루트 포스방식으로 푼다면 O(n^2)이 된다. 이는 정확성 풀이에서는 다 맞출 수 있지만 효율성 풀이에서 통과할 수 없다. 따라서 투포인터 방식으로 다음과 같이 풀어야 한다. 정답 코드 #include #include #include #include #include #include using namespace std; bool comp(pair a,pair b) { if(a.second-a.first == b.second-b.first) return a.first=gems.size()) break; m[gems[hi]]=hi; hi++; } } sort(v.begin.. 2020. 9. 6. 이전 1 다음