[백준/C++]13904번

티스토리 뷰

PS/백준

[백준/C++]13904번 - 과제

unside 2021. 3. 11. 17:19

박트리님의 게시글중 https://baactree.tistory.com/14?category=735523 를 참고해서 알고리즘을 공부하고 있다
지금 내가 보고 있는 부분은 알고리즘 초급...

초급 알고리즘 내용을 보니 https://blog.naver.com/kks227/220775134486 내용을 추천해줬다
그래서 해당 내용에 의해 탐욕적기법부터 공부하고 있다

오늘의 문제는!

https://www.acmicpc.net/problem/13904

입력

첫줄에 N이 주어지고 그다음 N개의 줄에 d와 w가 주어진다. d는 마감까지 남은 날, w는 해당 과제를 끝냈을 때 얻는 점수이다

풀이

처음엔 앞에서 부터 풀려고 했으나 선택지가 너무 많다 생각이 들어 바로 노선을 변경
뒤에서 시작하니 선택지가 많이 줄었다. 그래서 뒤에서 부터 풀기로 결정

현재 날짜를 day로 놓고 시작한다 처음 day는 d값중 제일 큰 수.
입력된 d의 값이 day보다 크거나 같으면 선택할 수 있는 선택지가 된다.

예를 들어 예제에서 보면 day 4일때 내가 선택할 수 있는 부분은 (6, 5), (4, 60), (4, 40), (4, 10)
(물론 내용을 진행해 보면 실제로 day 4에서 (6, 5)는 선택지에 없겠지만 단순히 day 4만 놓고 보았을때 저렇게 되는것이다)

그리고 선택지중 내가 실제로 고를 값은 당연히 점수가 가장 높은 (4, 60) 일 것이다.

소스

아래의 소스는 처음 문제의 정답을 맞춘 소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
 
struct data {
    int d;
    int w;
};
data inpArr[1000];
 
bool cmp(data a, data b){
    if(a.d==b.d){
        return a.w > b.w;
    }
    return a.d > b.d;
}
 
int main(void){
    int N;
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> inpArr[i].d >> inpArr[i].w;
    }
    
    sort(inpArr,inpArr+N,cmp);
    
    int day = inpArr[0].d;
    int sum = 0;
    while(day>0){
        int maxValue = 0;
        int maxIndex = -1;
        for(int i=0;i<N;i++){ //현재 날짜가 마감 날짜 보다 작으면 반복
            if(day <= inpArr[i].d){
                if(maxValue < inpArr[i].w){
                    maxIndex = i;
                    maxValue = inpArr[i].w;
                }
            }
            else{
                break;
            }
        }
        if(maxIndex != -1){
            sum = sum + maxValue;
            inpArr[maxIndex].w = 0;
        }
        day--;
    }
    cout << sum;
    return 0;
}
 
Colored by Color Scripter
cs

추가풀이

처음 문제를 풀고 소스를 다시 생각해보니 하나의 날짜 즉 같은 (4, 60) (4, 40) (4, 10)에서 내가 봐야하는 값은 가장 큰 값인 (4, 60) 뿐이다.
해당 내용을 좀 더 살펴보면 예를 들어 day 4에 값이 (4, 60) (4, 50) (4, 30) (4, 10) (5, 50) (5, 45) (5, 30) ... 이 존재 한다고 했을때 실질적으로 내가 비교하면 되는 값은 (4, 60) 과 (5, 50) 중 어느게 더 큰 값인가? 하는 것이다.
그래서 추가적으로 선택한것은 우선순위 큐로 최대힙을 사용했다.

아래는 해당 내용을 사용한 소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
priority_queue<int> inpArr[1000];
int main(void){
    int N, day = 0;
    cin >> N;
    for(int i=0;i<N;i++){
        int d, w;
        cin >> d >> w;
        inpArr[d].push(w);
        if(day < d){
            day = d;
        }
    }
    
    int sum = 0;
    int maxI = day;
    //끝날부터 앞으로 오면서 과제 선택
    for(;day>0;day--){
        int maxW = 0;
        int maxIndex = 0;
        for(int i=maxI;i>=day;i--){
            if(inpArr[i].empty()){
                continue;
            }
            else if(maxW < inpArr[i].top()){
                maxW = inpArr[i].top();
                maxIndex = i;
            }
        }
        if(maxW != 0){
            sum = sum + maxW;
            inpArr[maxIndex].pop();
        }
    }
    cout << sum;
    return 0;
}
 
Colored by Color Scripter
cs

저작자표시 비영리 동일조건

'PS > 백준' 카테고리의 다른 글

[백준/C++] 1493번 - 박스 채우기 (0)	2021.03.17
[백준/C++] 15748번 - Rest Stops (0)	2021.03.12
10989번 수 정렬하기 3 (0)	2019.06.27
2750번 수 정렬하기 (0)	2019.06.27
1475번 방 번호 (0)	2019.06.24

공지사항

최근에 올라온 글

최근에 달린 댓글

Total

Today

Yesterday

링크

« 2025/02 »
일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28

글 보관함

underside

티스토리 뷰