8/21 Problem Solving

오늘부터 연말까지 골드 문제 중에 랜덤으로 최소 5문제 이상씩 풀어보려고 한다. 골랜디가 80% 이상 방어되는게 목표다. 꾸준히 해보자..

 

 

1477 휴게소 세우기 (G4)

 

처음에는 priority queue를 이용해서 greedy하게 m번에 걸쳐서 제일 큰 구간을 반씩 자르면 될것이라고 생각했다. 근데 생각해보니까 한 구간을 여러번 분할하는게 답이 되는 경우도 있어서 이 접근은 틀렸다. 구간의 최댓값의 최솟값이 될 수 있는 범위를 후보로 놓고 parametric search를 해서 답을 찾으면 된다.

 

http://boj.kr/4481a6d19d05480db5e86a48da136770

 

 

2473 세 용액 (G3)

 

일단 정렬한 후에 모든 용액에 대해 하나의 용액을 fix하고 나머지 두 개의 용액에 대해서 투 포인터를 돌린다. O(N^2)

 

http://boj.kr/9ff8026cbeea4aa88a09eda518a7c31b

 

 

2143 두 배열의 합 (G3)

 

두 배열에 대해서 각각 모든 구간합을 구해놓는다. 한 배열의 구간합들과 해당 구간합의 개수를 map에 넣어놓고 다른 배열을 기준으로 목표값에서 현재 구간합을 뺀 값이 key값으로 map에 존재하면 counting해준다.

 

http://boj.kr/79efb151439a4eb3b04526012512a6d0

 

 

2457 공주님의 정원 (G3)

 

모든 꽃에 대해서 꽃이 피는 날짜가 빠를수록, 꽃이 피는 날짜가 같으면 지는 날짜가 느린 순으로 정렬한다. 그리고 3월1일~11월30일 구간에 대해서 greedy하게 앞에서부터 많은 구간을 차지하는 구간을 counting해준다. 아이디어와는 별개로 구현이 조금 까다로웠다.

 

http://boj.kr/3f7bd44b741c4f31ba3229c498d13781

 

 

2616 소형기관차 (G3)

 

dp1[i] = i번째까지 포함하여 길이가 m인 하나의 구간을 선택했을 때 얻을 수 있는 최대합

dp2[i] = i번째까지 포함하여 길이가 m인 두개의 구간을 선택했을 때 얻을 수 있는 최대합

dp3[i] = i번째까지 포함하여 길이가 m인 세개의 구간을 선택했을 때 얻을 수 있는 최대합

이라고 정의하고 구간들의 범위가 겹치지 않게 적절히 테이블을 채운다. 답은 dp3[n]이다.

 

http://boj.kr/0bbea28cf8a343a2a01f95e4db6d6664

 

 

20366 같이 눈사람 만들래? (G3)

 

전체 눈사람 지름을 정렬한다. 첫번째 눈사람의 두 덩이를 fix하고 두번째 눈사람의 두 덩이에 대해서 투 포인터를 돌리면서 차이의 최솟값을 찾는다. 시간 복잡도는 O(N^3)인데 N이 최대 600이므로 시간 내에 충분히 가능하다.

 

http://boj.kr/12e35c44e13e4a6d8601450187197bf4