[C++] 백준 13904번: 과제

2022. 9. 7. 02:00·problem solving/백준

🔗 문제

13904번: 과제

 

13904번: 과제

예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.

www.acmicpc.net

 

 

🖍 풀이

 

✔️ 최적의 해 구하는 방법

과제 점수가 높은 걸 챙기되, 최대한 마감일에 내면 된다.

 

과제 점수가 높다고 첫날부터 해버리면 안된다.

1 30, 5 100 일때를 생각해보자. 130점을 챙길 수 있는데 100점만 맞을 수도 있다.

 

또 하루에 한 과제만 할 수 있으니 visited[i]로 i 날 과제를 냈는지 안 냈는지 확인해줘야 한다.

 

 

+ 천재같은 사람을 봤다..

입력을 {-d, w} 받으면 비교 함수를 안 만들어도 된다.

 

 

💾  소스

#include <iostream>
#include <queue>
#include <algorithm>
#define MAX  1000

typedef std::pair<int, int> pii;
struct compare
{
    bool operator()(const pii& a, const pii& b)
    {
        if(a.second == b.second)
            return a.first < b.first;
        
        return a.second > b.second;
    }
};

int main()
{
    int N, d, w, answer = 0;
    bool visited[MAX+1] = {false, };
    std::vector<pii> v;
    
    std::cin >> N;
    for(int i=0; i<N; ++i)
    {
        std::cin >> d >> w;
        v.push_back({d, w});
    }
    
    //과제 점수가 높은 순으로 정렬
    std::sort(v.begin(), v.end(), compare());
    
    //과제 점수가 제일 높은 순으로 본다.
    for(const auto& [d, w] : v)
    {
        // 과제 낼 수 있는 당일에 내는데 만약 더 높은 점수가 그 날 냈다면.. 그 전날에 내자.
        for(int i=d; i>=1; --i)
        {
            if(!visited[i]) // i날에 낼 과제가 이미 정해져 있지 않다면
            {
                visited[i] = true;
                answer+=w;
                break;
            }
        }
    }

    std::cout << answer;

    return 0;
}
저작자표시 비영리 변경금지 (새창열림)
'problem solving/백준' 카테고리의 다른 글
  • [C++] 백준 17509번: And the Winner Is... Ourselves!
  • [C++] 백준 1493번: 박스 채우기*
  • [C++] 백준 15748번: Rest Stops
  • [C++] 백준 11000번: 강의실 배정
u1qns
u1qns
http://github.com/u1qns
  • u1qns
    개발 블로그
    u1qns
  • 전체
    오늘
    어제
    • 분류 전체보기 (173)
      • 회고 (1)
      • programming (17)
        • 개념 정리 (6)
        • CI CD (1)
        • 트러블 슈팅 (0)
        • 환경설정 및 팁 (7)
      • problem solving (155)
        • 개념 정리 (3)
        • 백준 (129)
        • SWEA (15)
        • 프로그래머스 (4)
  • 블로그 메뉴

    • 홈
    • 방명록
  • 링크

    • 깃허브
  • 공지사항

  • 인기 글

  • 태그

    boj
    투포인터
    DFS
    미해결
    SSAFY수료식
    완전탐색
    SWEA
    DP
    POW
    HELLOSSAFY
    삼성청년SW아카데미
    C++
    cmath
    cpp
    구현
    BFS
    되추적
    그리디
    백준
    SSAFY
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
u1qns
[C++] 백준 13904번: 과제
상단으로

티스토리툴바