주간 문제풀이 01 (백준 2543/3136/1741/20192/1665)

같이 PS하는 친구들과 주마다 P5 - P1 난이도의 문제 각 하나씩 푸는 것을 목표로 재활훈련 중이다.

??

P5 - 초고속철도

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

2543번: 초고속철도

문제: [l, r] 구간 N개가 주어지고, 이 중에서 subset을 고를 때, 겹치는 구간 pair라면 둘 중 하나는 subset에 포함해야 하는 제한이 있다. 가능한 모든 subset의 개수를 구하는 문제.

풀이:

이미 입력된 구간의 일부만 보고 답을 구해놨을 때, 여기에 구간을 하나 추가하는 것을 생각해 보자. 이때 기존에 구해놓았던 부분 문제의 답을 재활용할 수 있는 두 가지 경우가 있다.

- 새로 추가한 구간을 subset에 포함하는 경우: 기존에 가능했던 경우라면 모두 그대로 가능하다

- 새로 추가한 구간을 subset에 포함하지 않는 경우: 기존에 있던 구간 중 새로 추가된 구간과 겹치는 구간은 모두 반드시 subset에 포함해야 한다. 즉, 겹치는 구간을 빼고 나머지 구간들만 가지고 구한 답을 활용할 수 있다.

이 점을 이용해서 끝 점 기준으로 정렬하고, 각 구간을 추가할 때마다 앞 두 개 부분 문제의 답을 더하는 방식으로 해당 구간까지 봤을 때의 답을 반복해서 구하면 된다.

 

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

 

P4 - 평면도 

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

3136번: 평면도

문제:

좌표평면에서 상하좌우대각선 8개 방향 중 하나로 N번 움직였을 때, 선으로 완전히 둘러싸인 공간의 개수를 구하는 문제.

 

풀이:

오일러 공식 v+e-f=1 을 이용한다.

지나왔던 점들과 선들을 모두 기록하며 중복을 제거하면 v와 e의 값을 구할 수 있다.

이 때 대각선으로 지나온 길 두개가 교차하는 경우는, 정수 좌표는 아니지만 교차하는 점이기 때문에 적절히 v와 e의 값을 조정해주어야 하는 것을 유의하자.

 

코드: http://boj.kr/9a28d8e3aa88484aa0eac481bb117082

 

P3 - 반 나누기

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

1741번: 반 나누기

문제:

그래프에서 노드를 disjoint set으로 나누되, 서로 다른 set에 있는 노드 쌍은 모두 두 노드를 바로 잇는 간선이 있어야 하는 제한이 있다. 가능한 disjoint set 개수의 최대값을 구하는 문제.

 

풀이:

가장 간선이 적은 노드를 A라고 하자. 우선 A와 연결되어 있지 않은 노드는 모두 A와 같은 set으로 이어준다. 여기서 연결된 노드들을 X, 연결되지 않은 노드들을 Y라고 하자.

|Y| <= M / N 으로 작기 때문에, Y내부의 노드쌍 / X-Y를 가로지르는 노드쌍을 모두 검사하면서, 간선이 없는 쌍을 같은 set으로 이어준다.

 

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

 

 

 

P2 - 순서 섞기

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

20192번: 순서 섞기

문제:

배열 앞/뒤로 원소를 뺀 순서대로 새 배열을 만드는 것을 순서 섞기라고 한다. 순서 섞기를 몇 번 반복하면 배열을 정렬할 수 있는가?

 

풀이:

배열을 증가 -> 감소 -> 증가 -> 감소 -> ... 와 같은 구간들의 합으로 바라본다.

섞기 연산 중 앞에서 증가/감소 구간을 하나 빼오면 증가/감소가 그대로 유지되고, 뒤에서 구간을 빼오면 구간이 반전된다.

이걸 이용해서 앞과 뒤의 구간 타입이 다르면 구간을 하나로 합칠 수 있고, 결과적으로 한 번의 연산에 증감 구간의 개수를 대략 절반으로 줄일 수 있다.

 

코드: http://boj.kr/49e1a6439ef641b1b9dec9764496cba4

 

 

P1 - 화물 열차

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

1665번: 화물열차

문제:

N개의 화물 구간과 마주보는 M개의 화물 구간이 있다. M개의 화물 구간을 적절히 옮겨 N개의 화물 구간과 최대한 많이 겹치게 하자.

 

풀이:

한 화물 쌍이 공헌하는 겹치는 칸 수는 `0 -> 1씩 증가 -> 최대치에 도달 -> 1씩 감소 -> 0` 과 같이 변화한다. 이 공헌 그래프의 기울기를 모든 쌍에 대해서 합친 것을 구간을 훓으면서 관리할 수 있다.

화물쌍마다 기울기가 변화하는 지점은 최대 4개가 있어서, 각 위치에 기울기가 얼만큼 변하는지 미리 전처리해 둘 수 있다.

전처리 후에는 M개의 화물 구간을 한 칸 씩 옮기면서, 해당 위치에서의 {겹치는 칸 수, 기울기} 를 관리하면 된다.

 

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