SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 난이도 : D4 알고리즘 유형 : 조합, 완전탐색 풀이 시간 : 38분 문제 풀이 임의의 지렁이 두 마리를 매칭시킨 후 한 지렁이(A)가 다른 지렁이(B)가 있는 곳으로 가도록 할 때, 모든 지렁이들이 움직인 벡터 합의 최소값을 구하자. 벡터 합의 크기는 다음과 같다. $|V| = |(x, y)| = x * x + y * y$ 이 문제를 해결하기 위해서는 먼저 벡터의 개념을 알아야 한다.a벡터와 b벡터를 각각 지렁이의 위치라고 할 때, c벡터는 a지렁이가 b지렁이까지 이동한 거리가 된다. 여기서, 벡터의 합 공식으로 $\vec{b} = \vec{a} + \vec{c}..

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 난이도 : D4 알고리즘 유형 : DP, 누적합 풀이 시간 : 1시간 44분 문제 풀이 현수는 동현이에게 초콜릿 한 조각을 작은 두 조각으로 자를 때마다, 초기 큰 초콜릿에 있었던 건포도의 개수만큼의 수입을 받아야 한다. 동현이가 현수에게 지불해야 하는 건포도의 최소 양을 구하여라.  문제를 이해하기 위해 두번째 TC를 예시로 들어보면, 초기 상태에서 다음과 같은 방법으로 자를 수 있다.여기서 현수가 얻을 수 있는 수입은 나누기 이전의 건포도 개수만큼 받게 되고, 이런 방식으로 모든 초콜릿이 1 x 1 사이즈가 될 때까지 나누어야 한다.  해당 문제에 접근하기 위해서..

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 난이도 : D4 알고리즘 유형 : 완전탐색 풀이 시간 : 24분 문제 풀이 숙소에는 다음과 같이 긴 복도가 있고, 방이 서로 마주보게 배치되어 있다. 모든 학생들은 현재 위치에서 자신의 방으로 돌아가려고 하는데, 만약 두 학생이 자기방으로 돌아가면서 지나는 복도의 구간이 겹치면 두 학생은 동시에 돌아갈 수 없다.이동하는데는 거리에 관계없이 1 단위시간이 걸린다. 이 문제에서 가장 중요하게 생각해야 할 부분은 방은 서로 마주보고 있는 것이다. 이동하는 데 거리와 상관없이 1 단위시간이 걸린다고 하였기 때문에, 문자는 간단히 완전탐색으로 풀어낼 수 있다. 우선, 복도 배..

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 난이도 : D4 알고리즘 유형 : 완전탐색 풀이 시간 : 53분 문제 풀이 N개의 문제 중 틀리면 0점, 맞으면 배점만큼 점수를 받는다. 학생들이 받을 수 있는 점수의 경우의 수는 총 몇 가지인지 구하는 문제이다. 문제를 간단하게 생각해보면, 받을까 ? 받지 않을까 ? 에 대해서만 생각하면 된다. 하지만, 문제의 총 개수가 $N ≤ 100$이기 때문에, 단순히 완전 탐색을 사용한다면, $O(2^{100})$으로 시간초과가 나게 된다. 따라서, 점수를 하나씩 더해가며, 받을 수 있는 점수 배열에 추가한 다음, 중복되는 단어는 visited 배열을 통해 가지치기를 진행해..