백준 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..

사실 이 문제는 백준 19580번 "마스크가 필요해"와 완전히 접근방법이 동일하다. viyoung.tistory.com/171 [백준 19580번] [그리디/ 우선순위 큐] 마스크가 필요해 문제를 보고 생각보다는 쉽게 그리디 문제임을 파악할 수 있다. 문제 조건을 잘 보면, 최대한 많은 시민이 마스크를 구매할 수 있도록 유도해야한다. 즉 상식적으로 이 워딩을 보면 모든 시민들 viyoung.tistory.com 왜냐하면, 9676번과 19580문제에서 가장 Tight하게 해당 value를 만족하는 것을 선택한다는 핵샘이 동일하기 때문이다. 이전 19580문제 해설에서 언급한 것처럼 책을 가질 수 있는 scope를 increasing order로 정렬하고, 책 또한 번호를 증가시켜가면서 책을 가질 수 있는..

잘 생각해보면, 주유할 수 있는 양이 무한대이므로 최소 가격으로 넣을 수 있을 때 최대한 많이 주유하는 것이 유리하다. 다만, 문제가 되는 지점이 현재까지의 최소 가격을 어느 상황까지 커버할 수 있는지가 미지수이다. 예를 들어 지역 1, 2, 3, 4를 방문하는 상황이라고 하자 지역 1에서 현재 기름을 3의 가격을 판매하고 있다고 하자. 일단 적어도 지역 2까지는 가야하므로 최소한 지역2까지 가는데 필요한 거리에 필요한 주유량은 구입해야 한다. 하지만, 그 이상의 거리까지 구매를 해야하는지 여부는 지역2의 기름 가격을 알아야 한다. 지역 2의 기름 가격보다 싸면, 지역 1에서 지역2에서 지역3까지 가는데 필요한 기름을 미리 구매하는 것이 더 유리하다. 즉, 지역 2에서 3으로 갈 때 사용되는 기름의 가격..

사실 잘 생각해보면, 작은 숫자들을 순차적으로 뽑아주면 된다. 우선순위 큐를 활용해주어도 괜찮고, 전체 쿼리의 업데이트가 없으므로 배열을 정렬해줘서 하나씩 탐색하는 방식으로 처리해주어도 무방하다. 다만 0이 여러개 등장할 수 있는 지점만 조심해주면 된다. (맨 앞자리가 0이 될 수 없으므로 2번째 자리 이후부터 0을 배치하면 된다. 즉 첫 자리는 0이 아닌 숫자를 무조건 배치하고 0을 고려해주면 된다.) #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; while(true){ int n; cin >> n; vector data; if(n..

일단 이 문제를 보고 DP의 대표적인 유형인 Napsack문제를 떠올릴 수 있으나 가방 1개 당 보석 1개만 챙길 수 있다는 점에서 해당 문제와 차이점을 보이고 있다. 처음 접근한 방법은 다음과 같다. 만약 무게를 감당할 수 있다면 무조건 무게를 큰 것을 우선적으로 고르는 것이 유리하므로, 무게를 큰 순서대로 배치하고 감당가능한 무게이면 챙기는 방식으로 진행하였다. 다만, 이런식으로 진행하게 되면 최악의 경우 각 가방에서 N개를 전체탐색해야하므로 O(NM)이 나와 시간초과가 나오게 된다. 근본적으로 시간 초과가 나는 이유가 각 가방에 대해서 보석을 전체 탐색을 하기 때문이다. 발상을 바꿔서 무게를 우선적으로 고려하면, 가방의 한계 무게를 넘지 않는 것 중 가격이 최대인 것을 골라주는 것으로 문제를 바꿔 ..

여러가지 샘플을 만들어가면서 최적해를 구해보면 1. 남는 플러그 자리가 있으면 들어간다. 2. 없는 경우 다시 등장하는 것이 이후인 것부터 뽑는다. 만약 다시 등장하지 않는 경우는 해당 값을 INF로 처리해서 최우선적으로 뽑으면 된다. 적당히 현재 어느 숫자가 플러그에 꽂혀있는지를 저장해두는 배열을 만들고 관리해주면 된다. 추가적으로 순차적으로 데이터가 들어오고, 앞에서부터 다음 자리의 크기 비교를 해야하는 상황이므로 큐 자료구조를 활용하면 쉽게 풀 수 있다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; #define INF 987654321 int main(void){ ..

일단 주유소를 거리가 작은 것부터 정렬하고 해당 주유소를 갈 수 있는지 체크해준다. 만약 해당 주유소를 갈 수 있는 연료가 남았다면 일단 통과해주고, 없다면 이전에 있는 주유소 중 연료를 최대한으로 공급할 수 있는 곳을 방문했다고 간주해주면 된다. 계속해서 거리가 증가하는 방향으로 이동하고 있는 상황이므로, 결과적으로 모든 주유소를 방문해야 한다. 즉 각 주유소를 통과할 수 있는 연료가 남아 있는지 여부만 지속적으로 Greedy하게 체크해줘도 된다. 이전 주유소를 통과했다면 이전까지 도착하는데에는 연료가 충분했다는 것이므로 현재 주유소를 통과할 만큼의 연료만 있으면 되기 때문이다. 다만, 최소한으로 멈춰야하므로 연료 주입량이 많은 주유소에서 멈추는 것이 가장 이득이다. 만약 연료를 공급받지 않은 이전 주..