나코더 방학 연습 1주차 풀이

• • • 1. 3000번 버스
    • 2. 과제 안 내신 분..?
    • 3. Amalgamated Artichokes
    • 4. 카드
      • 방법 1.
      • 방법 2.
    • 5. 두 용액
      • 1. $O(NlgN)$ 방법
      • 2. $O(N)$ 방법
    • 6. 세 용액
    • 7. 팰린드롬 경로 3
    • 8. 레슬러
    • 9. 커플 깨기
    • 10. 램프
      • 1. Convex Hull을 이용한 방법
      • 2. 이분탐색을 이용한 방법

1. 3000번 버스

$\large{2^{k} - 1}$

2. 과제 안 내신 분..?

배열 a를 만든다.
x라는 숫자를 읽고 나면 a[x]에 체크한다.
이후 a 배열을 순회하며 체크되지 않은 x를 찾아 답을 출력한다.

문제 자체는 단순하지만, counting sort 등의 아이디어와 밀접하게 닿아있다.

3. Amalgamated Artichokes

영어라서 어려워 보이지만 읽어보면 쉬운 문제이다.
아래의 리빙포인트를 꼭 참고하자.

리빙포인트
문제가 영어라서 읽기 귀찮을 땐, 2~3번째 문단부터 읽어보자.

$price(k)=p(sin(ak+b)+cos(ck+d)+2)$ 라고 하자.
$1 \leq i < j \leq n$ 인 $(i,j)$ 중 $price(i)-price(j)$의 최댓값을 구하는 문제이다.

$price(k)$의 식이 복잡하기 때문에, 그냥 하면 실수 오차가 생기고 저 식을 잘 분석해서 정확한 값을 구하는 문제처럼 보일 수 있다.
하지만 그런 걸 요구하는 문제는 아니다.

어떤 i에 대해, $price(j)-price(i)$가 최대가 되는 j는, 1~(i-1)중 $price(j)$가 가장 큰 j일 것이다. 이러한 j를 일일이 찾으면 $O(N^{2})$ 풀이가 된다.
$O(N)$에 해결하기 위해서는 어떻게 해야 할까? i를 1부터 n까지 돌며, $\large \displaystyle \max_{j=0}^{i-1} \{price(j)\}$를 유지하고 있다면, 그 값과 $price(i)$를 비교하여 답을 갱신해주면 된다.
자세한 방법은 소스 코드를 참고하자.
소스 링크

4. 카드

STL 연습문제이다. long long을 써야 하는 것을 잊지 말자.

방법 1.

들어온 값들을 정렬한다.
정렬된 상태에서, 서로 같은 값들은 인접해있으므로, 배열을 돌며 그 길이를 잘 구해주면 된다.
소스 링크

방법 2.

std::map을 사용한다.
만약 이 문제를 2번과 같은 방법으로 푼다고 하자. 즉, x라는 값이 들어오면 a[x]에 1을 더해주고, 마지막에 전체를 순회하며 값을 검사한다고 하자.
이 방법의 문제는, 값의 범위가 너무 크다는 것이다. 값의 범위가 크기 때문에 모두 커버 가능할만큼 큰 배열을 잡는 것과 모든 값을 순회하는 것이 불가능하다.
std::map은 이러한 문제를 해결해준다. 사용방법은 직접 검색해보거나 소스를 보면서 익혀보자.
소스 링크

5. 두 용액

값을 정렬했다고 하자. 정렬하는 부분을 제외하고 봤을 때 시간복잡도가 다른 두 가지 방법이 있을 수 있겠다.

1. $O(NlgN)$ 방법

배열의 각각의 원소 x에 대해, -x와 가장 가까운 원소를 찾으면 된다.
즉, -x 이하인 것중 가장 큰 원소와, -x 이상인 것중 가장 작은 원소를 찾으면 될 것이다.
각각을 이분탐색으로 찾을 수 있다.
$N$개의 원소를 보며 $O(lgN)$의 시간이 걸리는 이분탐색을 수행하므로 총 시간복잡도는 $O(NlgN)$.

2. $O(N)$ 방법

위의 방법과 비슷하다.
만약 x에 대해 가장 가까운 원소 두 개를 찾았다고 하자.
x가 증가하면, 그 가장 가까운 원소들은 감소할 것이다.
즉, 가장 가까운 원소의 위치를 나타내는 값을 가지고 있고, x를 점점 증가시킴과 동시에 그 값을 필요한 만큼 줄인다.
x는 1에서 N까지, ‘가장 가까운 원소의 위치’는 N에서 1까지 감소할 것이고, 어떤 두 원소가 비교되는 횟수 또한 N에 비례한다.
따라서 전체 시간복잡도는 $O(N)$.

6. 세 용액

$N \leq 5000$이므로, $O(N^{2})$이 포함된 시간복잡도도 생각 가능하다.
어떤 두 용액 x, y를 잡았다면, -(x+y)에 가장 가까운 원소를 하나 찾으면 될 것이다.
이 때 주의할 점은, 그 원소들이 x나 y와 겹치지 말아야 한다는 것이다.
해당 원소를 이분탐색으로 찾으면 $O(N^{2}lgN)$이다.
x를 고정시키고, y를 증가시킴에 따라 가장 가까운 원소를 찾으면 $O(N^{2})$이다.
소스 링크

7. 팰린드롬 경로 3

일단 백트래킹이 생각나지만, 탐색해야 할 상태가 너무 많고, 시간 안에 나오지 못할 것이 자명한 것 같다.
이제 다르게 생각해보자. 경로가 팰린드롬이라는 것은,

• 시작점에 적혀있는 글자 = 도착점에 적혀있는 글자
• 두 번째 점에 적혀있는 글자 = 뒤에서 두 번째 점에 적혀있는 글자
• …

이런 꼴이어야 할 것이다.

입력으로 들어온 격자를 A라고 하자.
DP를 생각할 수 있다.

dp[a][b][c][d] = 시작점으로부터 (a,b), 도착점으로부터 (c,d)까지, 팰린드롬이 되도록 도달하는 방법의 수

A[a][b] ≠ A[c][d]이면 이 값은 자명하게 0일 것이다.
아닐 경우, 시작점은 (a,b-1) 혹은 (a-1,b)에서 오고, 도착점은 (c,d+1) 혹은 (c+1,d)에서 왔을 것이다.
각각의 값을 가져와주면 될 것이다.
길이를 고려해야 하는 것이 아닌가, 하는 생각이 들 수도 있겠다. 하지만 (1,1)에서 (a,b)까지 도달하려면 정확히 a+b-2번 움직여야 한다. (n,n)에서 (c,d)까지도 마찬가지로 2n-c-d번 움직여야 한다. 이 둘이 같기만 하면 상관이 없다. 만일 그 값이 $\left \lfloor \large\frac{L+1}{2} \right \rfloor$ 가 되었다면 답에 더해주면 될 것이다.
소스 링크

8. 레슬러

수여하는 금화 중, 각 선수가 승리한 경기의 수는 항상 일정하고, 레슬러들의 순서를 바꿔도 영향을 받지 않는다. 순서를 바꾸는 것은 자기보다 앞에 있는데 자기가 이긴 선수의 수에 영향을 주는데, 이 값을 최소화시켜야 할 것이다.
이 값을 0으로 만들 수 있을까…?

어떤 선수의 앞에는 자기가 지는 선수들만 있도록 배치할 수 있다면, 그 값이 0이 될 것이다. 이를 위해서는 세 선수 A, B, C가 있을 때, A가 B를 이기고 B가 C를 이긴다면, A는 C를 이긴다는 것이 필요하다. 이것이 가능하다면, 선수간에 이기고 지는 관계를 기준으로 정렬할 수 있다. 정렬된 상태로 배치하면 모든 선수의 앞에는 자기가 지는 선수들만 있도록 배치될 것이다.

이제 그것이 성립하는지 고민해보자. $P_{i}$와 $R_{i}$를 각각 $i$번째 레슬러의 ‘힘’과 ‘마술 링의 힘’이라고 하자.
A가 B를 이기는 조건은 다음과 같다.
$$P_{A} + R_{A}P_{B} > P_{B} + R_{B}P_{A}$$
정리하면
$$(R_{A}-1)P_{B} > (R_{B}-1) P_{A} \\ \frac{R_{A}-1}{P_{A}} > \frac{R_{B}-1}{P_{B}}$$
즉, $A$의 ‘경기력’은, 실제로는 상대에 영향을 받지 않고, 선수 고유의 값인 $\frac{R_{A}-1}{P_{A}}$ 에만 의존하게 된다. 이 값에 따라 항상 승부가 결정이 나게 된다. 때문에 A가 B를 이기고, B가 C를 이기면, 이들의 값의 크기 순서에 의해, 자명하게 A가 C를 이기게 된다.
즉 선수들을 승부 결과에 따라 정렬하면 된다! 여기서 우리가 A에 의존하는 값과 B에 의존하는 값을 서로 분리하려고 노력(했고 결국 성공)했다는 점을 곱씹어보자.

참고로, 이 값을 double로 들고 다니며 사용해도 된다! 값의 범위가 1000 이하이기도 하고, 만약 double의 오차가 중요해질 만큼 값이 비슷하다면 값이 같은 경우일 확률이 매우 높은데, 이 문제에서는 비기는 경우가 없다고 했기 때문이다. 하지만 double을 사용하는 것은 매우 매우 매우 매우 매우 위험하기 때문에, 꼭 쓰고싶은 경우가 아니면 되도록이면 쓰지 말자.

소스 링크
소스 링크(double 사용)

9. 커플 깨기

indegree

어떤 노드에 대해, 그 노드로 들어오는 간선의 수

outdegree

어떤 노드에 대해, 그 노드에서 나가는 간선의 수

degree

어떤 노드에 대해, 그 노드와 연결된 간선의 수.
방향 그래프에서는 보통 indegree + outdegree를 나타낸다.

무방향 그래프에서 모든 degree의 합은 항상 짝수이다.
증명 | 간선 하나가 degree의 합을 2씩 증가시키기 때문.

원하는 조건을 만족시키면

• degree가 홀수인 노드의 경우, indegree = outdegree ± 1
• degree가 짝수인 노드의 경우, indegree = outdegree

일 것이다.

만약 모든 노드의 degree가 짝수라면 어떻게 풀까?
모든 노드의 degree가 짝수라면 그래프의 각각의 component에 대해 항상 오일러 회로(Eulerian circuit, Eulerian cycle)이 존재한다.
오일러 회로란 한 정점에서 시작해 모든 간선을 지나고 다시 시작점으로 돌아오는 경로를 뜻한다.
오일러 회로를 쭉 돌며, 회로를 지나는 방향으로 간선의 방향을 고정해준다고 해보자.
그러면 모든 정점에 대해, 그 정점에 한 번 들어오면 한 번 나가게 되므로, indegree와 outdegree가 같아진다. 즉 문제에서 요구하는 조건을 만족하게 된다.

이제 degree가 홀수인 정점이 있다고 하자.
가상의 정점 $v_{0}$을 만들어, 모든 점을 여기에 연결해보자.
그러한 정점은 항상 짝수 개 있으므로, $v_{0}$의 degree 또한 짝수이다.
그리고 각각의 홀수인 정점 또한 degree가 1 증가하므로, 모든 정점의 degree가 짝수가 된다.
이제 위에서 말한 작업을 한 뒤, $v_{0}$과 그와 연결된 간선들을 제거했다고 하자.
각각의 홀수인 정점들은 indegree와 outdegree가 같은 상태였다가, $v_{0}$의 제거에 의해 indegree와 outdegree가 1 차이나게 된다.
각각의 짝수인 정점들은 변화가 없다.
따라서 문제에서 요구하는 사항을 만족할 수 있게 된다.
소스 링크

10. 램프

이웃한 점들을 이은 ‘직선’들을 생각했을 때, 모든 직선보다 위에 있는 점 중 y좌표가 가장 작은 것을 찾는 문제이다.

1. Convex Hull을 이용한 방법

직선들을 기울기 순으로 정렬한 후, stack을 이용하여 convex hull을 구할 수 있다.
그 후 convex hull을 이루는 이웃한 직선들간의 교점 중 y좌표가 가장 작은 것을 찾는다.
시간복잡도는 정렬의 $O(NlgN)$ + 처리 $O(N)$

2. 이분탐색을 이용한 방법

먼저, 어떤 높이 y에서 모든 지면을 비출 수 있다고 하자.
그러면 그 점에서 y좌표를 더 높이기만 하면 항상 모든 지면을 비출 수 있을 것이다.
그렇다면 이분탐색을 적용할 수 있게 된다.
‘높이 x에 램프를 놓아 모든 지면을 비출 수 있는가?’라는 질문에 대해 대답할 수 있다고 해보자.
최소 높이가 될 수 있는 범위 $[l,r]$을 놓고, $m=\frac{l+r}{2}$라고 했을 때,
$m$에 대해 그 질문에 대한 답이 yes이면 $r \leftarrow m$으로,
답이 no이면 $l \leftarrow m$으로 만들어줄 수 있다.
그러면 최소 높이가 될 수 있는 범위가 절반이 된다.
이 과정을 넉넉하게 50번정도 수행한다면, 이 범위는 ${1/2^{50}}$배가 되므로, 답을 거의 완벽하게 맞출 수 있다.

이제 ‘높이 x에 램프를 놓아 모든 지면을 비출 수 있는가?’라는 질문에 대해 생각해보자.
높이 x에 램프를 놓았다면, 어떤 직선에 대해 램프가 그 직선보다 위쪽에 있어야 하므로, 램프가 있을 수 있는 x좌표의 범위가 $(-\infty, p)$ 혹은 $(p,\infty)$ 꼴로 한정된다.
모든 직선에 대해 이러한 범위들의 교집합을 구했을 때, 그 교집합이 공집합이 아니라면, 그 집합 안의 어떤 점에 램프를 놓을 수 있다는 뜻이 된다. 즉 해당 교집합이 공집합이 아닌가의 여부를 대답하면 된다.

Written with StackEdit.