1680번 - 쓰레기 수거
몇 시간 붙들고있다가 전혀 모르겠어서 다른문제 풀어보고 다시왔는데도.. 잘 모르겠네요 ㅠㅠ
우선은 조금 무식하게 풀어보고 개선을 하려했는데 개선은 꿈도 못꾸게 생겼습니다..
제가 잘못생각하고 있는 부분이 있다면 지적 부탁드립니다.
문제에 그대로 쓰여있는 내용이긴 합니다만 이해를 제대로 했는지 모르겠네요. 이를 코드로 옮겨 적은게 아래의 코드입니다.
============================================================================================================
코드 설명
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 4
1 1
3 1
출력
26
16968
2
20
댓글을 작성하려면 로그인해야 합니다.
exponential_e 5년 전
몇 시간 붙들고있다가 전혀 모르겠어서 다른문제 풀어보고 다시왔는데도.. 잘 모르겠네요 ㅠㅠ
우선은 조금 무식하게 풀어보고 개선을 하려했는데 개선은 꿈도 못꾸게 생겼습니다..
제가 잘못생각하고 있는 부분이 있다면 지적 부탁드립니다.
문제에 그대로 쓰여있는 내용이긴 합니다만 이해를 제대로 했는지 모르겠네요. 이를 코드로 옮겨 적은게 아래의 코드입니다.
============================================================================================================
코드 설명
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