문제

연료 채우기

풀이

틀린 코드...

int l = Integer.parseInt(st.nextToken()); // 성경이의 위치에서 마을까지의 거리
int fuel = Integer.parseInt(st.nextToken()); // 트럭에 원래 있던 연료의 양
// 마지막 위치까지 도달하기 위함
q.add(new int[] {l, 0});

int answer = 0;
int current = 0; // 현재 위치
// 마지막 위치 전가지만 반복
while (q.size() > 1) {
	if (current >= l) {
		break;
	}

	int[] station = q.poll();

	fuel -= (station[0] - current);
	current = station[0]; // 현재 위치

	if (fuel < 0) {
		answer = -1;
		break;
	}

	if (current >= l) {
		break;
	}

	int[] next = q.peek();

	if (fuel < next[0] - current) {
		answer++;
		fuel += station[1];
	}
}

이 경우에는 모든 연료를 사용하지 않고 다음 연료만을 생각했기 때문에 반례가 존재한다. 결국 완전히 모자라게 될때 지난 정류장 중에 가장 많이 연료를 채울 수 있는 곳이 정답이 된다.

PriorityQueue<Intger> prevStation 
	= new PriorityQueue<>(Collections.reverseOrder());
    
while (!q.isEmpty()) {
	// 연료가 모자라지 않을때 연료를 제거 해준다.
	if (q.peek()[0] <= f + current) {
    	int[] station = q.poll();
        // 현재 연료 소진
        f -= (station[0] - current);
        // 현재 위치 변경
        current = station[0];
        // 지난 정류장들의 연료
        prevStation.add(station[1]);
    
    // 연료가 모자란데, 정류장에 충전할 연료가 있는 경우
    } else if (!prevStation.isEmpty()) {
    	// 연료를 충전
        f += prevStation.poll();
        answer++;
        
    // 충전할연료도 없고 연료가 모자란 경우
    } else {
    	System.out.println(-1);
    	System.exit(0);	
    }
}

System.out.println(answer);

전체 코드

전체 코드