문제 요약
앞에서 본 블럭의 개수와 옆에서 본 블럭의 개수가 배열로 주어졌을 때, 해당 배열을 사용해 쌓을 수 있는 블럭의 최소 개수와 최대 개수를 출력한다.
아이디어
입력의 크기
입력의 크기가 앞(이하 front), 옆(이하 side)이 각각 최대 100,000개이다. 만일 N^2로 탐색을 한다치면 10의 10승. 해당 크기의 배열을 만들면 분명 메모리 초과가 발생할 것이고, 해당 횟수만큼 탐색을 진행한다면 분명 시간초과가 발생한다.
그렇다면?
규칙을 찾아 단순 연산으로 문제를 풀이할 수는 없을까? 규칙을 찾으려고 애쓰던 도중, 정렬을 하면 뭔가 풀릴 것 같은 예감이 들었다. 각 칸에 해당하는 값을 출력하는 것이 아니라 총 개수를 출력하는 문제이기 때문에, 덧셈 연산을 통해 문제를 해결할 수 있지 않을까?
그렇다면 정렬이 가능한지, 즉 정렬을 해도 답이 달라지지 않는지부터 생각해보아야한다.
정렬을 해도 괜찮은가?
3차원은 헷갈리니까, 2차원으로 생각해보자.
위와 같은 2차원 배열이 존재한다고 하자. 가로 줄에는 front에 해당하는 값이, 세로 줄에는 side에 해당하는 값을 적었고, 배열의 각 칸에는 각 좌표에서의 높이를 기록한다.
세로의 인덱스를 i, 가로의 인덱스를 j라고 하자. 각 칸의 들어갈 값에 대한 조건은 다음과 같다.
(i, j)에 들어갈 수 있는 최대값은front[j]와side[i]중 더 작은 값일 것이다.- 또,
i열의 모든 값은side[i]의 값보다 커서는 안되는 동시에, 이 중 하나는side[i]의 값을 포함하여야한다.
이를 모든 각 줄에 대해 떼어내서 생각해보자.
만일 해당 열에 대해 행의 순서를 바꾸더라도, 필요한 조건은 변하지 않는다.
이를 모든 열, 행에 대해 적용해본다면, 결론적으로 모든 front, side 배열의 위치를 변환하더라도 결론적으로 블록의 합은 똑같이 적용된다는 것을 알 수 있다.
규칙을 찾아내기 위해, front와 side 배열에 대해 내림차순으로 정렬을 진행한 후 시작한다.
최소값의 규칙
위와 같은 배열에서부터 시작. 배열은 실제로 만들 필요 없다. 단순히 i와 j의 인덱스를 옮겨가며 연산을 진행하는 것으로 해결 가능하다.
블록의 합의 최소값을 찾을 때 감안할 점은, front 배열과 side 배열에 있는 값들을 모두 사용하면서 최소값을 찾는 것이다. 이 때, front와 side에 중복되는 것들을 모두 빼는 것이 관건이다.
최소값을 저장하는 변수로 minimum을 0으로 초기화해주었다.
조건 분기를 다음과 같이 나누어 볼 수 있다.
-
side[i] == front[j]
둘의 값이 같으므로 해당 값을minimum에 1번만 추가하면 된다.
i와j의 값을 모두 사용하였으므로, 각각의 값을 1씩 증가시킨다. -
side[i] > front[j]
큰 값을(i, j-1)에 넣는다.side[i]를minimum에 1번 추가한다.
현재 인덱스에 해당하는i의 값을 사용하였으므로,i의 값을 1 증가시킨다. -
side[i] < front[j]
큰 값을(i-1, j)에 넣는다.front[j]를minimum에 1번 추가한다.
현재 인덱스에 해당하는i의 값을 사용하였으므로,i의 값을 1 증가시킨다.
배열의 각 숫자에 대하여, '이 숫자를 채운다'를 감안하며 인덱스를 올려나간다고 생각하면 좋다.
사실 어느 인덱스에 어떤 값이 들어가는지는 중요하지 않다. 이 만큼의 블럭이 추가된다는 사실만이 중요하다.
예시
비교의 편의상 0을 추가해주었다.
이렇게 하면 위의 조건을 충족시키면서도 최소값을 유지하는 블록의 개수를 구할 수 있다.
최대값의 규칙
위의 배열을 마찬가지로 응용한다.
이번에는 최소값과 다르게, 많은 수의 블록을, 가능한 곳에 최대한 많이 배치하는 것이 목표다.
마찬가지로 i와 j의 인덱스를 늘려가며 블록의 수를 계산하는데, 지금 i와 j에 해당하는 값을 어느 범위까지 배치할 수 있는지를 생각해보아야한다.
배열을 내림차순으로 정렬했기 때문에, 현재 단계에서 최대한 많은 범위에 블록을 배치하는 방향으로 생각한다.
현재 i와 j 인덱스에 대해 탐색을 하고 있다는 얘기는, i-1와 j-1까지는 배열을 채웠다는 것이다(아래 예시를 보면 이해할 수 있다). 따라서 이미 채운 범위를 감안하고 계산식을 세워야한다.
설명의 편의를 위해 i와 j의 인덱스는 1부터 시작한다고 가정하고 설명한다. 코드의 구현시에는 1씩 빼는 방식으로 구현해야한다.
최대값을 저장하는 변수로 maximum을 0으로 초기화해주었다.
side[i] == front[j]
i*j - (i-1)*(j-1)만큼side[i]를 놓을 수 있다.
(i*j - (i-1)*(j-1)) * side[i]만큼을maximum에 증가시킨다.
현재의i와j에 대해 채울 수 있는만큼 블록을 채웠으므로 각각 1씩 증가시킨다.
side[i] > front[j]
side[i]의 값이 더 크기 때문에j열에는 해당 값을 배치할 수 없다.
아래 그림에 해당하는 행에만 값을 배치할 수 있는데, 이는j-1개이다.
따라서(j-1) * side[i]만큼을maximum에 증가시킨다.
side[i] < front[j]
front[j]의 값이 더 크기 때문에i열에는 해당 값을 배치할 수 없다.
아래 그림에 해당하는 행에만 값을 배치할 수 있는데, 이는i-1개이다.
따라서(i-1) * front[j]만큼을maximum에 증가시킨다.
예시
마찬가지로 예시에서는 배열에 값을 집어넣는 형식으로 나타냈지만, 들어갈 값과, 이 값을 넣을 수 있는 칸의 수를 계산해내기만 하면 된다.
불가능한 경우?
두 배열의 max값이 일치하지 않는 경우. 잘 생각해보면 해당 최대값을 배치할 수 있는 곳이 없으므로, 이는 불가능한 경우이다.
시간 복잡도
정렬에는 O(NlogN)만큼의 시간 복잡도.
대신 위의 최소값과 최대값을 찾는 방법은 side 배열과 front 배열을 한번씩 순회하면 되기 때문에, O(N+M)으로 해결이 가능하다.
구현
import sys
input = sys.stdin.readline
N, M = map(int, input().split(" "))
front = []
side = []
for i in range(N) :
front.append(int(input()))
for i in range(M) :
side.append(int(input()))
front.sort(reverse=True)
side.sort(reverse=True)
front.append(0)
side.append(0)
if front[0] != side[0] :
print(-1)
exit(0)
# minimum
i = 0
j = 0
minimum = 0
while i < N or j < M :
if front[i] == side[j] :
minimum += front[i]
i += 1
j += 1
elif front[i] > side[j] :
minimum += front[i]
i += 1
else :
minimum += side[j]
j += 1
if i > N :
i = N
if j > M :
j = M
# maximum
i = 0
j = 0
maximum = 0
while i < N or j < M :
if front[i] == side[j] :
maximum += front[i] * ((i + 1) * (j + 1) - i * j)
i += 1
j += 1
elif front[i] > side[j] :
maximum += front[i] * j
i += 1
else :
maximum += side[j] * i
j += 1
if i > N :
i = N
if j > M :
j = M
print("%d %d"%(minimum, maximum))