꼬리에 꼬리를 무는 형태이므로, 오일러 경로를 의심해 볼 수 있다. 동일한 컴포넌트 안에서 해당 정점과 연결된 간선이 홀수인 정점의 개수가 2k이면, 한붓그리기로 최소 k개의 경로로 만들 수 있음은 오일러 경로의 증명을 통해 논증할 수 있다. 다만, 오일러 회로의 경우, 해당 점점과 연결된 간선이 홀수인 정점의 개수가 0개임에도 불구하고 최소 1개의 경로로 만들 수 있으므로 예외처리 해야 한다. 즉, 해당 컴포넌트에서 최소경로는 max(해당 점점과 연결된 간선이 홀수인 정점의 개수 / 2, 1)이다. 또한 다른 컴포넌트간에는 따로 따져서 최소값끼리의 덧셈을 통해 구해주면 된다. 추가적으로 동일한 컴포넌트에 위치하고 있는지는 dfs와 visited배열을 활용해서 처리해주면 된다. #include #defi..

문제 상황을 파악하기 위해서 여러번 시뮬레이션 하다보면 기존의 Amart 위치에 Imart를 짓는 것이 가장 유리하다는 것을 파악할 수 있다. 이때 우선적으로 선택되는 Imart의 위치는 다음과 같다. 예를 들어 Amart가 1 3 5위치에 놓여있다고 하자. 만약 3번을 선택했을 때 얻을 수 있는 사람의 수는 (1~3 사이의 사람의 수 / 2 + 1~3사이의 사람의 수 % 2) + 자기자신 + (3~5 사이의 사람의 수 / 2 + 3~5 사이의 사람의 수 / 2)라는 것을 파악할 수 있다. (단, alpha는 0 or 1) Amart 사이에 Imart가 놓이게 될 경우, 거리가 더 가까운 위치의 mart를 가게 되므로 사이의 위치한 사람의 수 / 2가 골라지는 것은 자명하다. 다만, 추가적으로 modul..

처음에는 MAX값을 변수로 두고, 최종 결과까지 가면서 남아있는 체력이 0 초과하기 위한 범위를 구하고 이 중 최솟값을 출력하는 방식으로 구현하려고 하였다. 사실 구현 양상을 보면 충분히 가능해보인다. 다만, 다른 방법으로는 가장 최악의 경우 몬스터가 엄청 쎄고 용사는 매우 약하다고 가정해보면 123456개의 방에서 몬스터의 공격력은 1000000이고, 체력도 1000000인데 용사의 공격력은 1이라고 하면 이 경우 최대 hp는 이 3개의 값을 곱한 값이다. 즉, HP는 1과 위의 최대 hp 사이에 존재할 수 밖에 없는 것을 활용해서 직접 다 계산해주면 된다. 최대 HP를 k라 하면 시간 복잡도는 O(nlgk)이므로 충분히 시간안에 돌아간다. #include #define fastio ios_base::..

사실상 백준 2792번 보석상자와 다른 부분이 하나도 없다. 물론 정렬하기는 해야한다는 점에서 차이가 아얘 없지는 않다. viyoung.tistory.com/186 [백준 2792번] [이분 탐색] 보석 상자 잘 생각해보면, 특정한 수를 나누고 몫과 나머지와 관련있다는 사실까지는 쉽게 파악할 수 있다. 다만, 해당하는 숫자를 판단하기 위해서 10e9 숫자를 판단해야하는데 이 부분은 이분탐색으로 해 viyoung.tistory.com 특정한 숫자 간격을 얼마만큼 형성할 수 있는지를 묻는 것이므로 근본적으로 나눗셈과 관련이 되어있다. 적당히 몫과 나머지를 보고 연산을 해주면 된다. 기존에 있는 주유소에는 다시 설치할 수 없으므로 나머지가 0인 경우에는 몫에서 - 1개만큼의 신규 주유소를 지을 수 있는 것이고..

잘 생각해보면, 특정한 수를 나누고 몫과 나머지와 관련있다는 사실까지는 쉽게 파악할 수 있다. 다만, 해당하는 숫자를 판단하기 위해서 10e9 숫자를 판단해야하는데 이 부분은 이분탐색으로 해결할 수 있음을 알 수 있다. 추가적으로 만족하는 상황 중에 가장 작은 숫자를 찾는 것이므로 lower_bound를 물어보는 것이다. 따라서 lower_bound binary search를 진행해주면 된다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef long long ll; int main(void){ fastio; ll n, m; cin >> n >> m; vector ..

Moo(n)를 구성하는 것은 Moo(n-1)에 의해 결정된다는 것을 활용해서 분할 정복 아이디어가 떠올랐으면 충분하다. 다만, 이 문제에서 해당 자릿수를 만족하는 알파벳을 구하는 것이 핵심이므로 바로 분할정복으로 들어가지말고, Moo(n)에 해당하는 자릿수를 구해서 어느 Moo value 자리에 의해 알파벳이 결정되는지 판단해주면 된다. Moo(n)은 Moo(n- 1) + M + o * (n + 2) + Moo(n - 1)이므로 해당 자릿수가 앞의 Moo(n - 1) 위치인지, 가운데인지, 뒤의 Moo(n - 1) 위치에 있는지 판단해주면 된다. 만약 앞 뒤의 Moo(n - 1)에 존재하는 경우, 분할정복으로 처리해주면 되고 가운데에 있는 경우는 맨 처음 자리만 빼고는 o을 출력해주면 된다. 다만, Ba..

백준 14601번 샤워실 바닥 깔기 문제와 비슷한 느낌으로 처리하면 된다. viyoung.tistory.com/146 [백준 14601번] [분할 정복] 샤워실 바닥 깔기 (Large) 분할정복의 대표적인 예시인 L-트로미노 타일링 문제이다. (사실 그냥 풀라고 했으면 못풀었을 듯) 접근 방법은 다음과 같다. (자세한 내용은 wogud6792.tistory.com/64 참고) 1. 전체 타일을 4등분해서 viyoung.tistory.com 위의 문제와 14601번 문제의 공통점은 4개의 영역으로 나눠서 분할정복 한 뒤, 각각의 정보를 통해 전체 영역의 정보를 처리하는 것이다. 이 문제의 경우 안에 있는 element결과를 이용해서 바깥 부분에 괄호를 감싸야하므로 (좌상단정보 + 우상단 정보 + 좌하단정보..

생각해보면 쉬운데, 분할정복이 아직 익숙하지 않아 쉽게 발견을 못했다. 항상 모든 문제를 풀 때, 큰 문제를 작은 문제로 나눠서 풀 생각부터 진행해야 한다. 즉, 이 문제를 분할 정복 문제로 느끼기 위해서는 근본적으로 제일 큰 덩어리와 나머지 묶음들을 움직이는 것으로 이해했어야 한다. 그러면 분할 정복 문제로 파악할 수 있다. Divide and conquer하는 느낌을 잘 받아두도록 하자. 쪼개고 합해서 처리하고, 가장 작은 component는 직접 처리하는 양상을 이해해야 한다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; vector r..