주간 문제풀이 10 (BOJ 5552 / 10649 / 10777 / 5484)

BOJ 5552 - 걷는 산타클로스 (P5)

https://www.acmicpc.net/problem/5552

5552번: 걷는 산타클로스

문제: 바둑판 모양의 도로가 있고, N개의 집이 교차로에 위치해 있고, 산타클로스가 도로만 이용해서 모든 집에 선물을 배달해야 한다. 임의의 시작점에서 시작할 수 있고, 마지막 집을 제외한 모든 집은 배달 후 다시 시작점으로 돌아와야 한다.

풀이:

마지막 집 또한 시작점으로 돌아와야 한다고 한번 문제를 바꿔서 생각해보자. 그러면 최적의 시작점은 (모든 x좌표 중 중간값, 모든 y좌표 중 중간값) 이 된다.

 

마지막 점에서 시작점으로 돌아올 필요가 없다는 것은, 마치 마지막 집은 한 번만 방문하고, 나머지 집들은 두번 방문하는 것처럼 바꿔서 생각할 수 있다. 어떤 집을 한 번 방문할 지 선택하는 것은 모든 x좌표, 모든 y좌표들 중 딱 하나를 빼는 거니까, x좌표의 중간값, y좌표의 중간값이 최초의 중간값에서 최대 한 칸 이동할 수 있다.

 

즉, 최적의 시작점의 후보는 최대 4개이고, 이 4개의 시작점에 대해서 각각 배달에 걸리는 시간을 계산해서 시간이 가장 작은 점을 택하면 된다. 시작점이 고정되었을 때 마지막 집은 단순히 시작점에서 가장 먼 집으로 구하면 된다.

 

코드: https://www.acmicpc.net/source/share/de803fa816154d5c901a48f0f8188255

 

BOJ 10649 - 프리스비 (P4)

https://www.acmicpc.net/problem/10649

10649번: 프리스비

문제: 각각의 소에 키, 무게, 힘이 정해져 있다, 소 여러마리로 스택을 쌓아 키를 높일 수 있는데, 이 때 각 소는 소의 힘만큼의 무게를 들 수 있다. 목표는 스택을 쌓아서 키를 H 이상으로 높이는 것인데, 그러한 것 중에서는 쌓은 스택의 맨 위에 추가로 더 올릴 수 있는 무게를 최대화해야 한다.

풀이:

N <= 20임으로 bitmask dp로 접근할 수 있다.

“dp[bm] = 정확히 bm에 있는 소만 사용했을 때, 스택의 맨 위에 추가로 더 올릴 수 있는 최대 높이”로 정의해 보자. dp[bm]을 계산하는 방법은, bm에 있는 소마다 그 소를 맨 위에 놓는 경우에 어떻게 되는지를 submask의 dp값을 이용해 계산할 수 있다.

예를 들어서 `bm`에서 i번 소를 뺏을 때 `submask`가 된다면, 먼저 i번 소의 무게가 dp[submask] 보다 작거나 같으면 i번 소를 submask로 이루어진 소 스택 맨 위에 놓을 수 있다. 그러면 dp[bm]은 “dp[submask] - i번 소의 무게”와, “i번 소의 힘” 중 작은 값으로 갱신할 수 있다.

 

코드: http://boj.kr/a0ed750da75e4fe989461e2bb4909ccb

 

BOJ 10777 - 허니버터칩 (P3)

https://www.acmicpc.net/problem/10777

10777번: 허니버터칩

문제: N봉지의 허니버터칩이 좌에서 우로 나열되어 있고, 그 사이에 M봉지의 허니버터칩을 끼워 넣을 수 있다. 그렇게 한 후에 좌에서 우로 순서대로 걸어가면서 허니버터칩을 고르는데, 이 때 리스트에서 연속된 과자를 고를 수는 없다. 각 봉지의 과자 개수가 주어질 때, 가져갈 수 있는 과자 개수를 최대화하자.

풀이:

 M개의 추가 제공 봉지는 순서 무관하게 끼워넣을 수 있기 떄문에, 추가 제공 봉지 중에서는 무조건 가장 많이 있는 봉지부터 가져갈 수 있다. 즉 추가 제공 봉지의 입력 순서는 상관이 없고, 몇 개를 가져갈지만 알고 있으면 상태 관리가 된다. 이 점에 착안해서 아래와 같은 dp상태를 관리할 수 있다.

- dp[i][u][nu][t] = i번째 기본 봉지까지 봤고, 여기에 가져갈 추가 봉지 u개, 가져가지 않은 추가 봉지 nu개를 끼워넣었고, 마지막 봉지를 사용했는지 여부의 bool값은 t로 표현한다.

 

이렇게 상태를 정의하면 아래와 같은 4가지 상태 전이만 고려하면 충분하다.

- 사용하지 않을 추가 봉지를 맨 뒤에 끼워넣는 것

- 사용할 추가 봉지를 맨 뒤에 끼워넣는 것

- 기본 봉지를 하나 더 보면서, 해당 봉지를 사용하는 것

- 기본 봉지를 하나 더 보면서, 해당 봉지를 사용하지 않는 것

 

 

여기에 구현의 편의를 위해 한 가지 보조 상태 전이를 같이 사용할 수 있다.

- 마지막 봉지를 사용하지 않았지만, 사용한 것으로 치는 것

 

마지막 기본 봉지까지 다 본 후, 사용한+사용하지 않은 추가 봉지 개수의 합이 M인 상태들 중에서 dp값이 가장 큰 것을 골라서 답으로 출력하면 된다.

아래 링크된 코드의 L13~L23에서 이 다섯 가지 상태 전이가 각각 순서대로 코드로 표현되어 있는 것을 참고할 수 있다.

코드: https://www.acmicpc.net/source/share/98eeb4da79014770b65a09c072f7fe6c

 

BOJ 5484 - 정원 (P2)

https://www.acmicpc.net/problem/5484

5484번: 정원

문제: l*w개(l, w <= 250)의 정사각형 칸으로 분할된 정원이 있고, 장미는 총 n개 심겨 있다.(n <= 5000) 이 정원에 두 개의 겹치지 않는 직사각형 모양의 울타리를 쳐서 각 직사각형 영역 안에 있는 장미의 개수를 정확히 k개가 되도록 하면서, 울타리의 둘레를 최소화해야 한다.

 

풀이:

먼저, 가장 나이브한 솔루션부터 시작해보자. 모든 가능한 직사각형을 만들어보고, 정확히 k그루의 장미가 있는 직사각형들을 부분합 배열을 통해서 걸러내고, 조건에 맞는 직사각형들의 모든 pair를 순회하면서, 겹치지 않으면서 가장 둘레가 작은 pair를 찾으면,  직사각형을 걸러내는 데 W^4번 연산이 필요하고, 그 후 pair를 순회하는 데에 최대 W^8번 연산이 필요하다. 크게 직사각형을 찾는 과정이 있고, 찾아낸 직사각형들을 순회하는 과정이 있는데, 이 두 과정을 나눠서 최적화해보자.

 

직사각형을 찾는 과정: 가능한 직사각형의  모든 밑변은 약 W^3개가 있다. 각 밑변마다 장미의 개수를 정확히 k개가 되도록 하는 직사각형 중 가장 작은 직사각형은 최대 한 개 있을 것이고, 이 직사각형은 각 밑변마다 이분탐색으로 찾을 수 있다. 이렇게 하면 모든 직사각형을 걸러내는 데에 W^3log(W)번의 연산이 필요하고, 조건에 맞는 직사각형이 최대 W^3개가 된다.

 

찾아낸 직사각형들을 순회: 미리 각 행 / 열마다 왼쪽 / 오른쪽 / 아래 / 위로 있는 직사각형 중에 가장 둘레가 작은 직사각형을 미리 전처리해두자.  그러니까 예를 들어서 아래 사진에서 A에 대해서는 c2보다 더 오른쪽에 있는, 즉 빨간색 영역에 완전히 속해있는 B같은 삼각형 중 둘레가 가장 작은 것을 미리 각 행 / 열에 대해서 전처리해두는 것이다. 그러면 각 직사각형마다 네 개의 방향에 대해 모두 쿼리하면, 겹치지 않는 가장 작은 직사각형을 O(1)에 찾을 수 있다.

 

이렇게 하면 직사각형을 걸러내는 데 W^3log(W) + 전처리 후 모든 페어 순회 W^3 두 스텝에 거쳐서 문제를 풀 수 있다.

코드: https://www.acmicpc.net/source/share/20db1103c31142c69978ab62830ff7e8

 

BOJ 7040 - 밥 먹기 (P1)

https://www.acmicpc.net/problem/7040

7040번: 밥 먹기

문제: 소들이 1번부터 N번까지 번호순으로 일렬로 서 있다. 이 때 서로를 좋아하는 소 ML쌍은 최대한으로 떨어져 있을 수 있는 거리가 주어지고, 서로를 싫어하는 소 MD쌍은 최소한으로 떨어져야 하는 거리가 주어진다. 이 조건을 만족하면서 줄을 서는 게 가능한지 판단하고 / 가능하다면 1번 소와 N번 소의 최대 거리를 구해야 한다.

풀이:

접근방식 1

https://measurezero.tistory.com/414 를 참고했다.

각 소의 위치를 d[i]라고 하자. 이 문제에서는 d[i]에 아래와 같은 제약사항이 주어진다.

- 소들의 위치가 번호순이여야 함: d[i+1] - d[i] >= 0

- 좋아하는 소들: d[b] - d[a] <= D

- 싫어하는 소들: d[b] - d[a] >= D

 

여기에 있는 각 식은 모두 D[i] <= D[j] + W 꼴로 나타낼 수 있다. (순서대로: d[i] <= d[i+1] + 0 / d[b] <= d[a] + D / d[a] <= d[b] - D) 이는 그래프에서 최단거리를 구할 때 각 간선을 relax하는 동작과도 동일하다. 즉, 위 제한 그대로 대응되는 간선을 만들어서 벨만포드 알고리즘을 돌리면 제약사항에 맞는 d[i] 배열을 구할 수 있다. 그래프에 음수 사이클이 있으면 불가능한 것이고, 벨만포드가 찾아주는 최단거리는 곧 제약사항을 만족하는 가장 큰 거리값이기에, d[N]을 답으로 출력하면 된다.

 

 

접근방식 2

(덜 엄밀한 것 같지만, 일단 처음 접근할 때는 이 직관적인 방식으로 접근했어서 참고용으로 같이 적어둠. 두 방식 모두 최종 풀이는 동일함)

먼저, 서로를 좋아하는 소와 서로를 싫어하는 소 조건 모두 transitive한 조건이라는 점을 관찰하자. (예를 들어서 A와 B가 10 이내에 있어야 하고, B와 C가 5이내에 있어야 하면, A와 C는 15 이내에 있어야 한다) 이걸 그래프로 모델링해서, A가 B와 X거리 이내에 있어야 할 때 A -> B로 X길이의 간선을 그으고 최단거리를 구하면, 임의의 두 소 U와 V사이의 최대거리를 구할 수 있다. 

 

조건을 만족하면서 줄을 서는게 불가능한 경우는, 좋아하는 소 조건에 의해 U와 V사이의 최대 거리가 X인데, 싫어하는 소 조건에 의해서 U와 V사이의 최소 거리가 X보다 클 때 발생한다. 싫어하는 소 조건도 transitive하기 때문에, A와 B가 X거리 이상에 있어야 할 때 B -> A로 -X 길이의 음수간선을 그으면, 임의의 두 소 U와 V사이에 음수 사이클이 생기는지 여부를 기준으로 불가능 판정을 내릴 수 있다.

 

이렇게 각 좋아하는 소마다 앞으로 가는 양수간선, 각 싫어하는 소마다 뒤로 가는 음수간선을 그은 후에는, 각 소마다 i+1 -> i로 가는 길이 0의 간선을 추가해주어서, 각 인접한 소마다 최소 거리가 0이라는 사실을 그래프에 추가해준 후에, 벨만 포드 알고리즘을 이용해 이 그래프 위의 최단거리를 답으로 출력하거나, 음수 사이클을 찾았을 때 불가능 판정을 내리면 된다.

 

코드:  http://boj.kr/ebdc0798a99242d2aa209aab3c14657d