- 조건 시작과 끝 관찰하기
시작점에서 첫 충전소까지 거리 / 마지막 충전소에서 종착지까지의 거리 빼먹지 말자. ex) 0-10까지 정류소가 있고, 1, 3, 5, 7, 9에 충전소가 있으면 0(처음)-1-3-5-7-9-10(종착)까지 생각을 해야 각 정류소 간 거리인 1,2,2,2,1이 제대로 나온다.
- 케이스 바뀔 때 마다 변수 초기화!!!
제일 큰 for문 밖에 나가면 안 됨! 가장 밖이라도 케이스 테스트 도는 안쪽에 있어야 케이스 별로 초기화가 된다.
- for 문 range 인자 잘 보자 (i, j, k)!!!
- Greedy 알고리즘 판별
배수 관계거나 선택이 다음 선택을 가로막지 않는다면 greedy 가능 이 경우는 끝이 정해져 있고 앞에서 최대한 많이 가는 게 무조건 유리한 상황이었다. 아니면 일단 돌려보고 예외 쳐낼 수도 있고
- 경우의 수 쪼개보기
부가 준 해법: 충전소 거리 계속 더하다가 최대 충전 거리 넘으면 되돌아온다. 충전소 거리 계속 더하면 그게 최대 거리보다 작거나, 같거나, 큰데, 작거나 같으면 계속 더해나가면 된다. 반면 최대 거리보다 크면 충전 횟수 +1 하고, 충전 거리 넘어 되돌아왔으므로 임시 변수를 0으로 바꾸지 않고 넘치게 만든 주범으로 바꿔 다음 계산 때 다시 더해지게 한다.
T = int(input())
for i in range(1, T + 1):
knm = list(map(int, input().split()))
charge = list(map(int, input().split()))
charge.append(knm[1])
distance = [] # 케이스 바뀔 때 마다 초기화 때려야
answer = 0 # 케이스 바뀔 때 마다 초기화 때려야 (이것도 마찬가지...)
temp = 0 # 케이스 바뀔 때 마다 초기화 때려야 (이것도 마찬가지...)
for j in range (0, knm[2]+1):
if j == 0:
step = charge[j]
else:
step = charge[j] - charge[j-1]
distance.append(step)
for k in range (len(distance)):
temp += distance[k]
if temp > knm[0]:
answer += 1
temp = distance[k] #이 순간 나가지는 거 아닌가? -> 맞음
if distance[k] > knm[0]:
answer = 0
break
print (f"#{i} {answer}")