exponential_e   5년 전

몇 시간 붙들고있다가 전혀 모르겠어서 다른문제 풀어보고 다시왔는데도.. 잘 모르겠네요 ㅠㅠ

우선은 조금 무식하게 풀어보고 개선을 하려했는데 개선은 꿈도 못꾸게 생겼습니다..

제가 잘못생각하고 있는 부분이 있다면 지적 부탁드립니다.

  1. 쓰레기의 용량이 초과된다 -> 해당 지역의 쓰레기는 담지않고 쓰레기장으로 돌아가 비우고, 다시 해당지역으로 이동.
  2. 쓰레기의 용량이 딱 맞아 떨어진다. -> 해당 지역의 쓰레기를 담고 더이상 앞으로 가지 않고 쓰레기장으로 돌아가 비우고, 다음 지역으로 이동.
  3. 쓰레기 용량이 가득 차지 않았지만 더이상 갈 곳이 없는 경우 쓰레기장으로 돌아간다.

문제에 그대로 쓰여있는 내용이긴 합니다만 이해를 제대로 했는지 모르겠네요. 이를 코드로 옮겨 적은게 아래의 코드입니다.


============================================================================================================

코드 설명

spot 배열: 배열의 인덱스는 해당 지역의 거리를 나타내고, 배열 내의 값은 그 지역의 쓰레기 양을 저장합니다.

collect: 쓰레기를 수집한 총 거리를 반환합니다.

result: 총 차량이 움직인 거리입니다.

현 지역에서 쓰레기를 담을 경우 용량이 초과하거나 같은 경우에 [이제까지 왔던 거리(i) + 되돌아갈 거리(i)]를 여기에 더해줍니다.

(그리고, 용량이 초과한 경우엔 해당 지역에 다시 방문해야 하므로 i++를 하지 않습니다.)

spare 변수를 통해서 쓰레기가 가득 차지 않았음에도 종료되는(위의 3번 조건입니다) 경우, 값을 담아두었다가 반환시에 result에 i와 같은 방식으로 더해줍니다.

spare 변수는 3번의 조건이 아닌 경우에 즉, 용량이 딱 맞거나 초과하여 돌아가게되면 항상 0으로 초기화 해줍니다.

waste는 쓰레기차에 현재 담긴 값을 저장한 변수입니다.

============================================================================================================

자꾸 이런류의 문제에서 헤매는데.. 그리디 같기도하고.. 문제분류 자체가 잘 안되는것 같네요.

문제 이해가 잘못된것 일까요? 아니면 빼먹은게 있을까요.. 반례라도 들어주시면 감사하겠습니다.


예제는 잘 돌아서 아래는 제가 몇개 만들어 출력해봤습니다.

제가 위에 생각했던대로 계산해보니 맞는것 같은데, 틀린답이 있다면 피드백 부탁드립니다ㅠㅠ

입력

4

5 6

1 2

2 2

3 4

4 1

5 2

6 2

1000 4

99 123

104 7

1111 12

4242 1000

2 1

1 2

1 4

1 1

2 1

3 1

4 1

출력

26

16968

2

20

댓글을 작성하려면 로그인해야 합니다.