CodeForce #849 (Div. 4) G1. Teleporters (Easy Version)

---

a 에는 각 텔레포트를 사용하기 위한  비용들이 저장된다.

이 값들에 거리에 따라 1씩 증가시켜준 값이 a에 저장되게 해준다. (move right or left 시 1coin을 사용해야하므로.)

 

최대한 많은 텔레포트들을 사용해야하므로 가장 비용이 적은 텔레포트부터 사용해줘야하므로 오름차순정렬을 해주고

앞에서부터 현재 가지고 있는 coin과 비교해가며 텔레포트 가능한지 확인하고 가능하다면 텔레포트를 한다.

 

while문에서 tp < len(a) 를 써준 이유는 처음에 주어진 coin이 모든 텔레포트를 사용할 수 있을 때 인덱스 값이 벗어나지 않게하기 위함이다.

c >= a[tp] 부분은 현재 가지고있는 coin인 c 가 다음 텔레포트를 하기에 충분한지 확인하기 위함이다.

 

import sys
input=sys.stdin.readline
INF=sys.maxsize
t=int(input()) # 테스트케이스 수
 
for _ in range(t):
    n,c =map(int, input().split()) # 배열길이, 코인개수
    tp=0 # 텔레포트 횟수
    a=list(map(int, input().split())) # 텔레포트 비용
    for i in range(0, n):
        a[i] += (i+1) # 거리에 따라 가중치 더해줌
    a.sort() #오름차순 정렬 
    
    while tp < len(a) and c >= a[tp] : 
        c -= a[tp]
        tp+=1
        
    print(tp)