백준 - 17393 다이나믹 롤러 [이분탐색]

17393 다이나믹 롤러

1. 문제유형

• Binary Search

2. 자료구조

• ink (list): 잉크를 저장하는 리스트
• vis (list): 점도를 저장하는 리스트
• answer (list): 각 자리에서 최대 칠할 수 있는 타일 수를 저장하는 리스트
• pos (int): 현재 타일 위치의 잉크값
• l (int): 현재 위치의 바로 앞 타일 위치를 저장
• r (int): 타일의 가장 끝 위치를 저장
• mid (int): l,r의 중간값
• res (int): 현재 위치에서 칠할 수 있는 최대 타일 위치

3. 해결과정

• 아이디어는 현재 위치 ink값보다 작은값들 중 최대값의 위치를 찾는다.
• 현재 위치 + 1 부터 ink값보다 작은 최대값 위치까지의 값을 카운트한다.
• 이 거리가 현재 위치에서부터 칠할 수 있는 타일 수가 된다.

1. i=0부터 n-1까지 반복문을 돌며 각 자리에서 칠할 수 있는 타일 수를 카운트한다.
2. 현재 위치 i를 기준으로 l,r을 정의한 후 l <= r일 동알 반복문을 돌며 타일 수를 카운트한다.
3. 현재 잉크값보다 mid의 점도가 크다면 칠할 수 없다. r = mid-1
4. 현재 잉크값보다 mid의 점도가 작거나 같다면 칠할 수 있다. l = mid+1, res = mid 저장
5. 반복문이 끝난 후, i+1부터 res까지의 타일 수를 count한다. = res - (i+1) + 1
6. 각 위치별 칠할 수 있는 타일 개수를 출력한다.

import sys

n = int(input())
ink = list(map(int, sys.stdin.readline().split()))
vis = list(map(int, sys.stdin.readline().split()))
answer = []

for i in range(n):
    pos = ink[i]
    l, r = i+1, n-1
    res = i

    while l <= r:
        mid = (l+r)//2
        if pos < vis[mid]:
            r = mid-1
        else:
            l = mid+1
            res = mid
    answer.append(str(res-(i+1)+1))
print(' '.join(answer))