cho31250   7달 전

그리디 이용해서 풀어봤는데, 틀렸다고 나오네요ㅠㅠ

그리디로 풀면 안돼나요???

baactree   7달 전

그룹 게시판에 설명 있어요

plzrun   7달 전

캬 .. 벌써 솔루션까지..!

slanjdu   7달 전

??!

plzrun   7달 전

그리고 슬렉 아이디 만들어주세요 ㅋㅋㅋㅋㅋ

cho31250   7달 전

슬렉 아이디가 몬가요?ㅠ
그리고 코드에서 어디가 이상한지 알 수 있을까요ㅠ

baactree   7달 전

4 40

3

1 4 40

2 3 40

3 4 40


답 80 이에요

plzrun   7달 전

우리 그룹 게시판에서 슬렉관련 공지를 읽어주세요!

cho31250   7달 전

슬렉 계정 만들었습니다!

cho31250   7달 전

말씀해주신대로 정렬 다시 해서 해봤는데, 계속 오답이네요ㅠㅠㅠㅠ

도와주세요ㅠㅠ흐어어엉

plzrun   7달 전

먼저 박스를 정렬하는 부분부터 볼게요.
아마 2천개여서 문제가 생길지는 모르겠는데,
아무튼 보통 comp같은 함수는 레퍼런스를 붙여서 구현합니다. 저렇게 쌩짜(참조기호 안쓰고)로 받으면 비교할때마다 메모리를 잡아먹습니다.
그래서 다음과 같이 코드를 고쳐줍니다.


```cpp
bool comp(const BOX &a, const BOX &b) {
    if(a.end==b.end) return a.start < b.start;
    else return a.end < b.end;
}
```


위와같이 깔끔하게 써줄수도 있죠. 
질문 작성자 분이 쓴대로 하면, 현 문제에서는 문제가 없지만... a.start == b.start일 때는 아무것도 반환하지 못하는 경우도 있습니다. (아 그리고 별건 아닌데, 그냥 보통은 a, b라는 변수이름 대신에 rhs, lhs라는 변수이름을 많이 사용하졍? 그냥. .뭐 이건 맘에 드는거 쓰면 되니까...ㅎ)
그래서 첫번째 우선순위의 == 같음을 먼저 비교한 다음 두번째 우선순위를 처리해주고, 첫번째 우선순위가 != 인 경우에 첫번쨰 우선순위를 처리해주면 되겠습니다. (모든 비교 함수가 다 이런식입니다 ㅎㅎ)

그리고 틀린 경우를 알려드리자면,
6 60
5
1 2 30
2 5 70
5 6 60
3 4 40
1 6 40
위와 같은 경우입니다.
답은 150인데, 현재 소스는 120을 출력하고 있습니다.
즉, 처음 선택할때 1 6 40에 해당하는 40에서 30만큼을 선택하기 때문에
끝날때까지 택배 가방(님이 가방으로 표현하셔서 그렇게 얘기하겠습니다 ㅋ) 용량이 30으로 밖에 유지될 수 없어서
중간에 크게 옮겨실어나를수 있음에도 불구하고 계속 용량 30밖에 못사용하는거죠.

그럼 어떻게 하냐...
s에서 택배꾸러미를 받아서 e에서 택배를 내려놓는다고 할때
s에서부터 e-1까지 해당 택배꾸러미를 계속 들고 있어야 합니다. (e는 내려놓는곳이니까 제외하죠)
해당 택배꾸러미의 용량을 w라고 하면 s부터 e까지는 택배를 기본 여유용량 C에서 w만큼 뺀 것입니다.
즉, 예를 들면 원래 가방용량이 40이고 s=2 e=4라고 하고 들고다닐 택배꾸러미 용량w=20이라고 하면 (택배를 주고받는 곳이 6개 있다고 합시다)
1    2    3   4   5   6
40 20 20 40 40 40 <-이 됩니다. (각 지점에서의 가방의 여유용량)

그럼 다음번에 1-4구간에서 택배용량이 30만큼 되는걸 나르려고 해도 2-3구간의 여유용량이 20밖에 되지 않으므로 20만큼만 나를 수 있습니다.

그리고 이러한 알고리즘이 가능하게 된 것은 처음에 도착지점을 기준으로 오름차순 정렬을 하기 때문입니다. (두번째 우선순위로는 출발지점을 기준으로 오름차순 정렬인거죠)
그니까 이 문제는 도착지점이 1쪽에 가까울수록.. 그니까 택배를 어디서 받았든간에(출발지점이 어떻든간에) 1에 가까운 도착지점에 택배를 내릴 수록 더 많은 택배를 실어날을 수 있습니다.

저도 우리 슬렉의 private channel(가입하신 스터디그룹 ㅋ)에서 잘 몰라서 계속 물어보고 풀었던 문제입니다.
저두 도움 많이 받아서 글 좀 남겨봤습니다 ㅎ;
슬렉 자주 들어오세요~!

아 그리고 정보올림피아드 문제의 경우는 http://www.jungol.co.kr/bbs/board.php?bo_table=pba... 여기 사이트 가서 회원가입하시고 제출하시면 틀린 테스트케이스가 뭔지 보여줍니다. 틀린 테케를 생각하는것도 능력이겠지만... 그냥 연습때에 틀린테케 보는건 정신건강에 아주 이롭다고 생각됩니다.ㅋㅋ

cho31250   7달 전

아 해결됐네요ㅠ 너무 감사드립니다! 설명이 이해가 잘가네요!

slanjdu   7달 전

설명 진짜 잘하신다 흐규흐규

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