백준 문제 풀이

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

19491번: Equation

n의 범위는 1~ 10^18입니다.

f(n)은 n의  디짓의 스퀘어 제곱인데,

디짓의 개수는 최대 19개입니다 (10^18면 공이 18개)

모든 디짓이 9일 때가 최대인데,

그때 f(n)의  범위는 1~81*19=2000입니다.

k에 대하여 f(n)의 값을 1부터 2000까지 for loop를 돌면서 모든 f(n)을 생각합니다.

k. * f(n)으로 n을 계산합니다.

계산한 n을 바탕으로 다시 f(n)을 f(n)의 정의대로 역산하여,

추정한 f(n)과 진짜 f(n)이 맞을 경우만 세서 리턴합니다.

 

long long이여도 10^18이면 아슬아슬하므로, for 루프에서 k * f(n) <= b 조건을 추가해주어서 오버플로우를 빠져나옵니다.

 

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

19488번: Championships

어떤 도시의 degree가 d 미만일 경우, 애초에 이 도시는 S에 포함될 수 없습니다.

하나하나 이런 도시들을 모조리 제거합니다.

 

그럴 경우, 그래프는 모두 degree가  d보다 크거나 같은 도시들만 남게 됩니다.

이 도시들은 이어져 있거나, 이어져 있지 않을 것입니다.

유니언-파인드로 서로 이어져 있는 도시들을 그룹핑하고,

그룹  중에서 크기가 가장 큰 도시를 리턴합니다.

 

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

24024번: 삼색 그래프

 

그래프의 일부 엣지에 가중치를 더하는 과정은,

최단 거리를 증가시키기만 하지 감소시키지 않습니다.

따라서 X스푼 모두를 집어넣는 것이 최단 거리를 최대화하는 비법입니다.

 

1번 정점과 2번 정점만 존재하고, 1번과 2번에 빨간색과 파란색 두 개의 엣지로 연결되었다고 해 봅시다.

그럼 빨간색과 파란색 둘 중 하나에만 가중치를 더하기보다는

가중치를 반 나누어 구하는 것이 이득입니다.

이를 통해, 가중치 분배의 함수는 단조 증가 혹은 단조 감소하지 않으므로,

이분 탐색으로 구할 수 없음을 추론할 수 있습니다.

 

삼분 탐색을 통해 X스푼을 빨간색에 a스푼, 파란색에 X-a스푼 넣는다고 가정할 때,

그때의 최단 거리를 다익스트라의 알고리즘으로 빠르게  구합니다.

이를 반복하여 최단 거리의 최대값을 계산합니다.

 

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

19808번: Guess the Path

풀지 못했습니다.

 

무작위로 대충 경로를 풀고 나오는 답을 대조하면 

[진짜 경로] [가짜 경로] 일 때,

 

[진짜 경로] [가짜 경로]

[진짜 경로]

를 추론할 수가 있습니다 (R으로 못가니 반드시 D로 가야 함)

 

또한

[가짜 경로] [진짜 경로] 이면

 

                  [진짜 경로]

[가짜 경로] [진짜 경로]

입니다.

 

이를 이용해서 가능한 추론해 가는 방식으로  짰는데,

10회 이내로  못 구하나 봅니다; 아니면 버그가 있던가..

http://boj.kr/3f549fd5bbb141ad9efdcf9c04ec0382

공유 소스 보기

틀린 코드 좀 봐야할 듯.

 

 

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

7981번: 장비를 정지합니다

 

처음엔 dp[i] = i번 장비를 정지하는 데 걸리는 최소 와트 로 정의합시다.

직관적으로 보았을 때 dp[i] = zi (강한 충격으로 정지했을 때) 입니다.

 

또한 dp[i] = wi + dp[gi,1] +... + dp[gi,  ri] (약한 충격으로 정지했을 때) 입니다.

 

최초에는 모든 dp[i] = zi 로 둡니다. 이는 최소 전력입니다.

버퍼를 하나 더 두는데, weak_dp[i] = wi  + dp[gi,1] +... + dp[gi,  ri] 

로 둡니다. 이는 약한 충격으로 i를 정지시킬 때 최소 전력입니다.

 

다익스트라로 갱신합니다.

weak_dp[i]가 dp[i] 보다 작아지는 경우,  (weak_dp[i], i) 를 큐에 넣습니다.

 

큐를 빼면서 dp[i]를 weak_dp[i] 만큼 갱신하고, 

i가 이 relaxation으로 얼마만큼 전력량이 최소화되나 diff를 구합니다.

이  diff만큼 다른 weak_dp[j] = wj + dp[gi, 1] + ... dp[i] + dp[gj,  rj] 

(약한 충격으로 닫을 때 i도 닫아야 하는 j) 도 값이 줄어드니, 갱신됩니다.

갱신된 값이 dp[j]보다  작아질 경우, 역시큐에 넣습니다.

 

이런 변형된 다익스트라를 반복시킨 후, dp[1]을 리턴합니다.

 

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

17154번: Dead-End Detector

 

1. 꼴이 트리일 경우,  리프의 개수가 dead-end-detector입니다.

2. 안에 사이클이 있을 경우,  사이클에 붙은 트리들의 root의 개수가 dead-end-detector입니다.

 

2를 구하기 위해서, 그래프를 vector<set<>> 으로 선언하고,

  degree가 1인 vertex들을 하나씩 반복적으로 떼어냅니다.

이러면 순수하게 사이클을 구성하는 그래프들만 남습니다.

 

이 사이클이 남는 그래프중에서, 이미 떼어진 간선의 개수를 세어서 리턴합니다.

 

1번 경우는 따로 포레스트를 flood-fill로 떼서 리턴합니다.

 

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

16183번: Electronic Circuit

 

그래프가 나이스  서킷인 경우,

최소한 한 엣지가 초단순 직렬이거나 병렬일 수밖에 없습니다. base case입니다.

이 base case를  지워나가며 남는 게 한 엣지면 nice circuit입니다.

 

병렬의 경우, 두 노드에 두 엣지가 겹쳐 등장합니다. 이는  그래프를 vector<set<>> 으로 구성하는 것만으로도 지워낼 수 있습니다.

직렬의 경우, 세 노드에 두 엣지가 연이어 등장합니다.

중간 노드를 안전하게 뺴내려면 이 중간 노드는 양 노드 말고 다른 연결고리가 없어야 합니다.

따라서  중간 노드의  degree는  2입니다.

이런 중간 노드를 모조리 찾아내어 제거하고, 양 노드를 잇는 새로운 엣지를 그으면 

직렬을 단순화할 수 있습니다.

이를 반복적으로 하여 답을 구해냅니다.