12-21 Merry problem solving!

2018 merry problem solving!

12-21 : Day1

boj 슬랙에서 koosaga님이 진행하시는 2018년 연말 merry problem solving 스터디(앳코더 문제들 매일 목표 정해놓고 풀기)에서 푼 문제에 대한 정리글. 풀이는 내가 풀기 쉬웠던 문제부터 어려웠던 문제까지 순서대로 나열되어 있다.

Code festival 2016 final A. Where's Snuke? (100 pts)

n * m 크기의 테이블이 주어지고 여기서 snuke라는 문자열이 있는 위치를 찾는 문제다.

풀이

100점짜리 문제인 만큼 딱히 쓸 풀이가 없다. 그냥 시키는 거 그대로 테이블에서 위치 찾아서 출력하면 끝.

ARC 90 D. Pepole on a Line (400 pts)

x 축 상에 N명의 사람이 서 있다. 같은 위치에 여러 명의 사람이 서 있는게 가능하고, M개의 (l, r, d) 정보가 주어진다. 이 뜻은 r번째 사람이 l번째 사람으로부터 x축 증가하는 방향으로 d만큼 떨어져 있는 위치에 있다는 말이다. 이 때, 주어진 M개의 정보를 만족하게 N명의 사람을 세우는 방법이 있으면 Yes, 아니면 No를 출력하는게 문제.

풀이

(l,r,d) 를 l->r에 거리 d, r->l에 거리 -d인 엣지가 있는 걸로 생각하고 그래프를 구성하면 쉽게 풀 수 있다. 아직 방문하지 않은 정점 중 아무거나 하나를 골라서 그 정점의 위치를 0이라고 생각하고, dfs를 수행하면서 edge에 적힌 거리 d에 따라 나머지 정점들의 위치를 결정해준다. 이 때 모순이 발생하면 No고, 모든 경우에 대해 모순이 발생하지 않으면 가능한 것이므로 Yes를 출력하면 끝.

ARC 97 D. Equals (400 pts)

1~N까지의 숫자로 이루어진 크기 N짜리 순열이 주어진다. 그리고 M개의 (i,j) 쌍이 주어지는데, 이 (i,j) 쌍에 대해서는 i번째 위치와 j번째 위치에 있는 수를 서로 바꾸는 연산을 수행할 수 있다. 수행할 수 있는 연산 횟수에는 제한이 없고, 이 연산을 이용해서 주어진 순열을 적절히 바꿔 i번째 수가 i인 위치의 개수를 최대한 많게 만들고 싶다. 가능한 최대 개수는 몇 개일까?

풀이

서로 위치를 바꿀 수 있는 임의의 (i,j) 쌍을 두 정점 i, j 간에 간선이 있는 것으로 생각해보자. 이러한 쌍을 통해 서로 오갈 수 있는 위치끼리는 숫자들의 위치를 마음대로 바꿔줄 수 있다(버블 소트를 생각해보자). 따라서, 이런 (i,j) 쌍을 통해 서로 이동가능한 정점끼리 묶어두면 그 정점 내에 있는 숫자들은 원하는 위치로 보내 줄 수 있으므로, 이렇게 구성된 컴포넌트 내에서는 항상 원하는 위치에 원하는 숫자를 둘 수 있다. 따라서, 각 컴포넌트마다 그 컴포넌트에 인덱스 i와 순열의 값 i가 모두 들어가 있는 경우의 개수를 세 주면 된다.

ARC 91 D. Remainder Reminder (400 pts)

N 이하의 수 (a,b)가 있다. 근데 이 수가 뭔지는 모르고, a를 b로 나눈 나머지가 k보다 크거나 같다는 것만 안다. 이러한 조건을 만족하는 쌍의 개수를 구하여라.

풀이

수학 문제. 나머지가 k보다 크거나 같아야하므로 일단 반드시 b >= k + 1이어야 한다. 이제 k+1 부터 n까지의 b에 대해서 가능한 a의 개수를 구해서 모두 더해주면 답을 얻을 수 있다.

이 때 어떤 임의의 b값에 대해서, a를 b로 나눈 나머지 0..b-1은 b를 주기로 반복된다. 따라서, n / b 만큼의 0..b-1이 반복되는 구간이 있다고 생각할 수 있다. 이러한 구간에서 a를 b로 나눈 나머지가 k이상인 경우의 개수는 (b - k)개 만큼이 있을 것이고, 따라서 이렇게 완전히 반복되는 주기는 그 주기 개수 * (b-k) 만큼을 답에 더해주면 된다. 그리고 마지막에 짜투리로 남는 일부 나머지에 대해서 그 나머지 r이 k이상이면 r-k+1을 다시 답에 더해주면 된다. 풀이 쓰고 보니 이게 위에 두 문제보다 더 쉬운 것 같은데...? 구현에 따라 예외 처리때문에 고생을 좀 할 수 있어서 이 것 때문에 개인적으로는 위 두 문제보다 살짝 까다로웠다.

ARC 95 D. Binomial Coefficients (400 pts)

N개의 서로 다른 수가 주어진다. 이 수들 중에서 두 개의 수 a, b (a > b)를 뽑을 것이다. 이 때, a개 중에 b개를 뽑는 경우의 수 C(a,b)가 최대가 되게 뽑았을 때의 a b를 출력하라.

풀이

처음에 서로 다른 두 C(a,b)와 C(c,d)를 어떻게 비교하지 하고 생각하면서 잘못 접근해서 시간을 좀 썼다. 배열의 숫자 크기 제한이 10^9 범위이기 때문에 실제로 C(a,b)를 구해서 비교할 수는 없고, 다른 방식의 접근이 필요하다.

조금만 생각해보면 두 가지 성질 때문에 답을 쉽게 찾을 수 있다.

1. C(a,b)에서 a값을 고정했을 때, b는 a/2에 근접할 수록 C(a,b)값은 증가한다.

2. C(a,b)에서 b값을 고정했을 때, a값이 커지면 C(a,b) 값도 커진다.

2번 성질 때문에 답에서 a값은 항상 배열 내에 존재하는 수중 최댓값이 될 수 밖에 없다. 만약에 a가 배열의 최댓값이 아닌 경우가 답이 된다고 가정하면, 그 경우에 a를 배열의 최댓값으로 바꿨을 때 2번 성질에 의해 답도 더 커지게 되고, 따라서 이러한 가정은 모순이 되기 때문이다.

이제 a값을 고정시킬 수 있으므로, 1번 성질에 의해 b값은 a/2에 제일 가까운 값인 경우가 답이 된다. 이러한 값을 탐색해서 찾아주면 C(a,b)가 최대가 되는 (a,b) 쌍을 찾을 수 있다. 정렬에서 O(nlogn), 그 다음 탐색에서 O(n) (혹은 이분탐색으로 O(logn))의 시간이 걸리므로 총 O(nlogn) 시간에 해결 가능.

ARC 83 D. Restoring Road Network (500 pts)

N개의 정점으로 이루어진 무방향 연결 그래프가 있다. 이 그래프의 모든 두 정점 i,j에 대해 그 두 정점의 최단거리 D(i,j)가 주어진다. 이 때, 해당 최단거리 조건을 만족하는 그래프를 구성할 수 없으면 -1, 구성할 수 있으면 그 경우에 대해 만들 수 있는 전체 엣지 거리합의 최솟값을 출력하라.

풀이

못 풀어서 결국 답을 봤다. 그래프 / construction 둘 다 약한 나의 단점이 너무 잘 드러난 문제였다... 이런 문제들을 좀 많이 풀어보면서 필요한 사고방식이나 접근법을 익힐 필요가 있을 것 같다.

우선 construction 문제에서 항상 제일 먼저 고려해야 할건 어떤 경우에 문제가 요구하는 케이스를 만들 수 없는가에 해당하는 조건을 찾는 것이다.

여기서, 주어진 D(i,j)는 반드시 i와 j사이의 최단거리여야한다. 따라서, 플로이드 쌍 알고리즘에서 최단거리 구하는 것과 유사한 방식으로 생각해보면, 임의의 D(i,j)와 정점 k에 대해, D(i,k) + D(k,j) 는 항상 D(i,j) 이상이어야 한다. 그렇지 않다면 i->j로 갈 때 i에서 k를 거쳐 j로 가는게 거리가 더 짧아져 버려서 D(i,j)가 최단거리가 아니게 되니까.

따라서 이러한 경우가 있다면 조건을 만족하는 그래프를 만들 수 없으므로 -1을 출력해야 한다.

그러면, 이런 경우가 없다면 항상 조건을 만족하는 그래프를 만들 수 있을까? 이는 D(i,j)를 엣지 길이로 하는 완전 그래프를 구성하면 항상 가능하다는 것을 알 수 있다. 모든 i, j에 대해 D(i,j)를 길이로 하는 엣지가 사이에 존재하므로 D(i,j) 조건은 만족할 수 있고, 또 모든 D(i,k) + D(k,j)는 D(i,j) 이상이므로 항상 이러한 D(i,j)가 두 정점간의 최단거리임도 만족하기 때문이다.

이제 조건을 만족하는 엣지 최단거리를 구해야하는데, 이 때도 마찬가지로 -1을 출력해야 하는 조건을 역으로 이용한다. 어떤 두 정점 i, j에 대해, D(i,j) = D(i,k) + D(k,j)를 만족하는 어떤 정점 k가 있다고 가정하자. 이 경우 i에서 j로 직접 연결된 간선은 만들 필요가 없다. i->k->j로 이동했을 때에도 D(i,j) 조건을 만족시켜 줄 수 있기 때문이다. 반면에, D(i,j) = D(i,k) + D(k,j) 조건을 만족하는 정점 k가 존재하지 않는 경우는 어떤 중간 정점을 거친다 하더라도 D(i,j)값에 해당하는 최단거리로 이동할 수 없기 때문에, D(i,j)를 길이로 하는 엣지를 반드시 추가해줘야만 한다.

따라서, D(i,j) = D(i,k) + D(k,j)를 만족하는 k가 존재하지 않는 모든 (i,j)쌍에 대해 D(i,j) 값을 더해주면 그게 곧 답이 된다.