문제 출처:https://www.acmicpc.net/problem/13904
13904번: 과제
예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.
www.acmicpc.net
항상 아이디어 생각하는게 힘들고 오래걸리는거 같다...
1. 입력부분에서 마감시간, 과제점수를 입력받는데 입력받으면서
제일 큰 마감시간을 기억해두었다가 해당 값을 길이로 하는 결과 계산용 배열을 만든다
2. 입력받은 마감시간, 과제점수을 과제점수를 기준으로 내림차순 정렬해준다
3. 아이디어는 - '점수가 높은 애들은 무조건 하고싶은데 어떻게 될지 모르기때문에 될 수 있으면 마감시간에 가깝게 처리한다'
4. 3을 바탕으로 구현 ㄱㄱ
사이트의 예제입력을 점수 내림차순 정렬하면
4 60
2 50
4 40
3 30
1 20
4 10
6 5
로 정렬되고 맨 위 데이터부터 결과 계산용 배열에 넣어보자 (결과 계산용 배열은 왼쪽이 1 오른쪽이 6이다)
기본적으로 마감시간에 넣고 마감시간에 이미 데이터가 있다면
마감시간 인덱스의 앞쪽으로 이동하면서 자리가 있는지 찾는다
이렇게 하면 배열 세팅은 (코드는 점수만 넣지만 글에선 [시간 점수] 형태로 작성함)
[], [], [], [4 60], [], []
[], [2 50], [], [4 60], [], []
[], [2 50], [4 40], [4 60], [], []
[3 30], [2 50], [4 40], [4 60], [], []
[3 30], [2 50], [4 40], [4 60], [], [6 5]
이런식으로 배열이 차게되며 이제 이걸 다 더하면 답을 구할 수 있게 된다
ps 거의 똑같은 문제가 2019번에 있으니 공짜점수먹자!