문제 바로가기
문제:
인팅 전문 회사 부키치 암즈는 거대한 페인팅용 롤러 "다이나믹 롤러"를 출시하였다. 이 신제품은 평범한 페인팅 롤러와 마찬가지로 굴려서 칠할 수 있지만, 손잡이를 세로로 휘둘러 잉크를 한번에 흩뿌릴 수도 있도록 설계되었다. 이러한 새로운 사용방법은 거대한 몸집과 맞물려 매우 역동적으로 보였기 때문에, 이 롤러의 이름은 다이나믹 롤러가 되었다. 평소 페인팅에 관심이 많던 멩미는 다이나믹 롤러의 매력에 흠뻑 빠져, 단숨에 다이나믹 롤러를 구매했다. 지금 당장 롤러를 시험해 보고 싶었던 멩미는 통로 일부분을 칠해보기로 했다. 통로는 1 × N 길이의 일자 형태를 가지고 있고, 통로의 바닥은 1 × 1 타일로 가득 차있다. 각 타일은 잉크지수 Ai 와 점도지수 Bi 를 가지고 있다. 타일이 제각각 다른 특성을 가지고 있기 때문에, 멩미는 세심하게 롤러를 휘둘러야만 한다. 멩미가 i 번째 타일 위에 서 있을 때, 멩미는 다이나믹 롤러로 현재 위치보다 오른쪽에 있으면서 점도지수가 서 있는 칸의 잉크지수 Ai 이하인 칸을 칠할 수 있다. 통로는 기본적인 관리가 되고 있기 때문에, 각 칸의 잉크지수 Ai 는 점도지수 Bi 이상이다. 그러나 깊숙한 통로는 관리에 어려움이 있기 때문에, 점도지수 Bi 는 항상 오름차순이다. 이런 상황 속에서 멩미가 통로의 각 타일에서 서 있을 때 다이나믹 롤러로 칠할 수 있는 최대의 칸 수를 구해보자.
입력:
첫 번째 줄에 통로의 길이인 자연수 N이 입력으로 주어진다. (1 ≤ N ≤ 5 × 105) 두 번째 줄에 N개의 정수 A1, A2, ..., AN이 공백으로 구분되어 주어진다. Ai 는 i 번째 칸의 잉크지수를 의미한다. (1 ≤ Aᵢ ≤ 1018) 세 번째 줄에 N개의 정수 B1, B2, ..., BN이 공백으로 구분되어 주어진다. Bi 는 i 번째 칸의 점도지수를 의미한다. (1 ≤ Bᵢ ≤ 1018, Ai ≥ Bi) B1, B2, ..., BN은 오름차순이다. 즉, 1 ≤ i ≤ j ≤ N을 만족하는 모든 정수 순서쌍 (i, j)에 대해 Bi ≤ Bj 가 성립한다.
출력:
첫 번째 줄에 N개의 정수 x1, x2, ..., xN을 공백으로 구분하여 출력한다. xi는 i 번째 칸에 서서 다이나믹 롤러를 사용할 때 최대로 칠할 수 있는 칸의 개수이다.
풀이 :
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
N = int(input())
lst_A = list(map(int,sys.stdin.readline().rstrip().split(" ")))
lst_B = list(map(int,sys.stdin.readline().rstrip().split(" ")))
result = []
for i in range(0,len(lst_B)-1):
now = lst_A[i]
start = i+1; end = len(lst_B)-1
res = i
while start <= end:
mid = (start+end) // 2
if now < lst_B[mid]:
end = mid -1
else:
start = mid +1
res = mid
result.append(str(res-(i+1)+1))
result.append(0)
print(*result)
이분탐색 문제이다.
start를 lst_a보다 한칸 더 앞에서 시작한다.
res는 칠할 수 있는것이다.
90은 5개 100은 5개 88은 3개 이런식인데
이 전에 있는것들은 색칠 할 수 없으므로 그것을 빼주는것이다
그리고result에 더하기 위해서 i+1부터의 res까지의 갯수를 세어준다.
댓글