주간 문제풀이 11 (BOJ 13308 / 4016 / 6989 / 2601)

미방

BOJ 13308 - 주유소 (P5)

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

13308번: 주유소

문제: N개의 도시와 M개의 도로가 있고, 각 도시에는 주유소가 있다. 1번 도시에서 출발해 N번 도시로 갈려고 하는데, 차의 기름통은 무한하다. 1km마다 1리터의 기름을 필요로 하고, 각 도시의 리터당 기름 가격이 주어지고, 도로의 길이가 주어질 때, 최소 비용을 계산하자. 

 

풀이:

풀이 1

각 도시에서 다른 모든 도시로 나가는 (도시의 기름 가격) * (다른 도시까지의 최단거리) 길이의 간선이 있다고 생각하고 다익스트라를 돌리자. 이렇게 하면 모든 도시에서 다른 도시로 가는 최단거리를 알아야 하기 때문에, 최소 가격을 구하는 다익스트라 1번 외에도 최소 거리를 구하는 다익스트라를 모든 노드에 대해서 N번 돌려야 한다.

시간복잡도는 NMlog(N)이고, 시간이 상당히 빡빡하게 도는 걸로 봐서는 정해는 아닌 것 같다..

 

코드: https://www.acmicpc.net/source/share/1de32428100241469851401824749ee7

공유 소스 보기

 

풀이 2

생각해보면, 그래프를 탐색하면서 여태까지 도달했던 도시 중 가장 싼 주유소에서 기름을 산 것처럼 취급해도 문제가 없다(연료통이 무한하니까). 그래서 (도시 번호, 여기까지 도달할 때까지 본 가장 싼 주유소의 가격) 를 상태로 잡고, 이 N^2개의 노드가 있는 그래프 위에서 각 상태로 도달하기 위한 최소 비용을 구하는 다익스트라를 돌리면 된다.

도시번호가 i고, 가장 싼 주유소 가격이 c일 때, j번 노드로 간다면, 이동한 상태에서의 가장 싼 주유소가격은 min(c, cost[j])가 되고, 비용은 기존에서 c*(간선 거리) 가 추가되는 식이다. 즉 dp[j][min(c, cost[j])] 에 dp[i][c] + c * (간선 거리) 를 relax해 주자.

 

시간복잡도는 비슷하게 NMlog(N)인 것 같은데, 이게 좀 더 빨리 돈다.

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

공유 소스 보기

 

BOJ 4016 - 모빌 (P4)

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

4016번: 모빌

 

문제: 이진 트리를 닯은 모빌이 주어지고, 이 모빌에서 이진 트리의 internal node에 해당하는 막대의 왼쪽 / 오른쪽에 달려있는 노드를 바꿔서 포화 이진 트리를 만들 수 있는지 여부와, 총 몇 번 바꿔야 하는지 묻는 문제.

풀이:

주어진 이진트리에서 모든 장난감(leaf node)가 같은 레벨에 있다면, 답은 0이다. 만약 레벨 차이가 2 이상 나는 장난감이 있다면 불가능하다. 이 두 가지 기본 케이스를 먼저 걸러내자.

 

모든 레벨 차이가 1이 난다면, 입력 방식 특성상 레벨이 작은 리프노드 하나 -> 0, 레벨이 큰 리프노드 두개 -> 1 이런 식으로 리프노드의 배치를 문자열 하나로 인코딩할 수 있다. (ex. 아래 그림처럼, 예제 데이터는 0111이 됨)

이 문자열의 길이는 2^N 꼴이 되는데, 이제 이 문자열을 통해서 최상위 레벨의 막대를 바꿔야 하는지 판단할 수 있다.

- 1의 개수가 절반 이상이면, 문자열의 왼쪽 절반이 1이 되어야 함

- 1의 개수가 절반보다 적으면, 문자열의 오른쪽 절반이 0이 되어야 함

이 조건을 만족시키기 위해서 왼쪽 절반과 오른쪽 절반을 바꿔야 한다면 답이 1 증가하고, 바꿀 필요 없다면 답은 그대로 둔다. 균일하지 않은 나머지 절반으로 재귀적으로 내려가면서 반복하면 된다.

 

코드: http://boj.kr/06ddd9e47a504a60806e558a657b7029

공유 소스 보기

 

 

BOJ 6989 - 채점 (P3)

문제: N개의 문항이 있는 답안지를 채점하는데, 각 문항에는 배점이 있고, 일반적으로는 각 문항마다 배점만큼의 점수를 받을 수 있지만, 연속해서 문항을 맞췄을 경우 전 문항에서 받은 점수를 같이 받을 수 있는 규칙이 있다. 이 때, K보다 크거 나 같은 정수로서 총점으로 나올 수 없는 가장 작은 점수를 구해야 하는 문제다.

풀이:

특정 문항을 맞췄다는 사실이 다음 문항에도 영향을 주기 때문에, dp로 문제를 풀 때 앞에서 몇 개의 문항을 풀었는지를 dp 상태 내에서 고려하거나, transition방식에서 고려해야 한다. 여기서는 transition에 녹이는 방식을 사용한다.

 

dp[i][pt] = "i번 문항까지 고려했고, i번 문항을 틀렸을 때, pt점을 받는 것이 가능한지 여부" 로 정의한다. dp[i]를 계산할 때(즉, i번 문항까지 봤을 때 가능한 점수들을 계산할 때) 가능한 transition이 두 종류 있다.

- i-1번 문제도 틀렸다: dp[i-1]의 값을 그대로 가져오면 된다.

- i-1번 문제는 맞췄다: i-1번 문제에서 j번 문제까지(1 <= j <= i-1) 연속으로 맞춘 경우에 대해, "dp[j-1]에서 가능한 점수들"에 "[j, i-1]구간의 문제를 맞췄을 때의 점수"를 더해서 나온 점수들은 dp[i]에서도 이제 가능하다.

 

이 때, dp[i]를 bitset으로 정의하면 메모리 사용량도 줄어들고, 대부분의 연산이 bitset shift / bitset or연산으로 치환되기 때문에, 시간초과를 피할 수 있다.

 

코드: http://boj.kr/8d68c55c9b9546938cb25cd951a6ee1a  

공유 소스 보기

 

 

BOJ 2601 - 도서실카펫 (P1)

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

2601번: 도서실카펫

문제: N개의 직사각형이 주어지고, 주어진 크기의 정사각형 하나로 최대한 많은 직사각형을 완전히 덮어야 한다.

 

풀이:

(주어진 정사각형의 크기를 K라고 하자. 점이 (r, c)처럼 row, column기준으로 주어진다고 생각하고 설명)

 

먼저 row기준으로 스위핑하자. r를 늘리면서 [r, r+K] 사이에 row가 완전히 들어오는 직사각형들을 유지한다.

그리고 구간에 들어오고 나가는 직사각형을 사용해서 "현재 row에서는 정사각형의 왼쪽 끝 column을 어디로 해야 가장 많은 직사각형을 포함할 수 있을까?"에 대해 답변을 해줄 range increment, maximum query 세그먼트 트리를 유지해준다.

 

좀 더 자세히는, 구간에 들어온 직사각형 각각에 대해, "해당 직사각형을 완전히 포함하도록 하는 정사각형의 왼쪽 c좌표"는 하나의 구간일테니, 이 구간에 대해서 세그먼트 트리에 구간 업데이트로 +1을 더해준다. 구간 밖을 나가는 직사각형에 대해서는 해당 업데이트를 롤백해준다. 보고 있는 r을 늘리고, row 구간에 들어가고 나가는 직사각형에 대한 처리를 마친 다음에는, 해당 세그먼트 트리의 maximum값이 해당 row에서의 정답이 되고, 전체 row에서의 maximum을 한 번씩 구해서 최대치를 출력하면 된다.

 

코드: http://boj.kr/4f376f3279ef45baa8dfb148e73fe818

공유 소스 보기