로봇 대회

면접 대비

시간 제한1초메모리 제한1024 MB

요약

N×N 격자에서 각 행과 열의 가장 높은 탑 높이가 주어질 때, 격자에 놓인 큐브 총 개수의 최솟값과 최댓값을 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 구현, 수학, 행렬
정답자: 아직 제출이 없습니다

문제

로봇 대회에 출전할 로봇을 만들었다. 로봇이 풀어야 하는 과제 중 하나는 정사각형 격자에 놓인 큐브의 개수를 세는 것이다. 격자는 $N$ 개의 행과 $N$ 개의 열로 이루어져 있고, 각 칸에는 $1$ 개부터 $5$ 개까지의 동일한 큐브가 쌓여 있다. 안타깝게도 이 로봇은 정보를 모으는 능력이 좋지 않다. 로봇이 할 수 있는 일은 각 행과 각 열에서 가장 높은 더미의 높이를 알아내는 것뿐이다. 그래서 로봇 자체를 아주 똑똑하게 만들어 이 문제를 해결하려 한다. 로봇이 모은 정보가 주어질 때, 격자에 놓인 큐브 개수의 최솟값과 최댓값을 계산하는 프로그램을 작성하라.

입력

첫째 줄에 격자의 행과 열의 개수 $N$ 이 주어진다. 둘째 줄에 $N$ 개의 정수 $r\_i$ $(1 \leq r\_i \leq 5)$ 가 주어지는데, 이는 $i$ 번째 행에서 가장 높은 더미의 높이이다. 셋째 줄에 $N$ 개의 정수 $c\_i$ $(1 \leq c\_i \leq 5)$ 가 주어지는데, 이는 $i$ 번째 열에서 가장 높은 더미의 높이이다. 입력에는 모순이 없음이 보장된다. 즉, 주어진 값을 만족하는 큐브 배치가 항상 하나 이상 존재한다.

출력

격자에 놓인 큐브 총 개수의 최솟값과 최댓값을 나타내는 두 정수를 출력한다.

제한

$3 \le N \le 10$

힌트

이 세 가지가 첫 번째 예제에서 가능한 유일한 배치이다. 앞의 두 배치는 큐브가 총 14개이고, 세 번째 배치는 총 15개이다. 따라서 큐브 총 개수의 최솟값은 14, 최댓값은 15이다.

예제2

예제 1
입력
```
3
2 3 1
3 1 3
```
예상 출력
```
14 15
```
예제 2
입력
```
4
5 5 5 5
5 5 5 5
```
예상 출력
```
32 80
```