백준 - 11977 Angry Cows [이분탐색, 브루트포스]

11977 Angry Cows

1. 문제유형

• 이분탐색, 정렬, 브루트포스

2. 자료구조

• n (int): 건초의 수
• bay (list): 건초의 위치를 담은 리스트
• cur (int): 현재 건초의 위치 인덱스
• rad (int): 폭발 사정거리
• l (int): 옮겨 붙을 왼쪽 건초 좌표 인덱스
• r (int): 옮겨 붙을 오른쪽 건초 좌표 인덱스
• cnt (int): 폭발시켜 태운 건초의 최대값

3. 해결과정

• ⭐왼쪽으로 옮겨 붙는 경우와 오른쪽으로 옮겨 붙은 경우를 나누어 구했다.
• ⭐왼쪽으로 옮겨 붙을 때는 터뜨린 가장 왼쪽 건초 index까지 count한 후 rad를 증가시킨다.
• ⭐오른쪽으로 옮겨 붙을 때 역시, 터뜨린 가장 오른쪽 건초 index까지 count한 후 rad를 증가시킨다.

1. 0번째 건초부터 n-1번째 건초까지 아래 과정을 반복한다.
2. l을 현재위치-1로 설정 후왼쪽으로 불태운 건초 개수를 구하는 과정을 반복한다.
3. 반복 종료 조건은 l<0 (더 이상 건초 없음) or bay[cur]-bay[l]>rad (폭발 사정거리 밖)인 경우이다.
4. 반복 종료 조건이 아니라면 l>=0 and bay[cur]-bay[l]<=rad(폭발 사정거리 안 일 경우)동안 cnt 개수를 증가시킨다.
5. 4번 과정이 끝나면 현재 위치를 왼쪽 건초로 이동한 뒤 rad를 1증가시킨다.
6. 오른쪽 건초에 대해서도 2-5과정을 반복한다.

4. 소스코드

n = int(input())
bay = list(int(input()) for _ in range(n))
bay.sort()

answer = 0

for i in range(n):
    cur, rad = i, 1
    cnt = 1
    l = cur-1

    while True:
        if l < 0 or bay[cur]-bay[l]>rad:
            break
        while l >=0 and bay[cur]-bay[l]<=rad:
            cnt += 1
            l -=1
        cur = l+1
        rad += 1

    cur, rad = i,1
    r = cur+1

    while True:
        if r >= n or bay[r]-bay[cur]>rad:
            break
        while r<n and bay[r]-bay[cur] <= rad:
            cnt += 1
            r += 1
        cur = r-1
        rad += 1

    answer = max(answer, cnt)
print(answer)