코딍코딍
코딩기록
코딍코딍
전체 방문자
오늘
어제
  • 분류 전체보기 (271)
    • 개발 (2)
    • Java (1)
    • 스프링 (28)
    • JPA (11)
    • Git (3)
    • 알고리즘 (160)
      • 백준 (132)
      • 프로그래머스 (8)
      • SWEA (20)
    • 토이 프로젝트 (14)
      • 간단한 Springboot CRUD (1)
      • 게시판 프로젝트 (13)
    • 알고리즘 개념정리 (8)
    • 오류 해결 (13)
    • 보류 (0)
    • AWS (5)
    • 트러블 슈팅 (0)
    • 회고 (3)
    • CS (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

최근 글

티스토리

hELLO · Designed By 정상우.
코딍코딍
알고리즘/백준

13904번 : 과제

알고리즘/백준

13904번 : 과제

2023. 8. 3. 12:00

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

 

13904번: 과제

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

www.acmicpc.net

 

문제

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

 

입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

 

출력

얻을 수 있는 점수의 최댓값을 출력한다.

 


소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int arr[][] = new int[n][2];
        int maxday = 0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            if (maxday < arr[i][0]) maxday = arr[i][0];
        }

        int sum = 0;
        int idx;
        int max;

        for (int i = maxday; i > 0; i--) {
            max = 0;
            idx = -1;
            for (int j = 0; j < n; j++) {
                if(i <= arr[j][0]) {
                    if(max < arr[j][1]) {
                        max = arr[j][1];
                        idx = j;
                    }
                }
            }
            if(idx != -1) {
                sum += max;
                arr[idx][0] = -1;
            }
        }

        System.out.println(sum);
    }
}

 

해결방법

하루에 하나의 과제만 끝낼 수 있고 마감일이 지난 과제는 점수를 얻지 못한다. 이때, 점수의 최댓값을 구하는 문제이다.

 

처음부터 탐색을 하면 경우의 수가 너무 많다. 1일차에 택할 수 있는 과제가 많기 때문이다.

고로, 뒤에서부터 탐색을 하였다. 그러면 해당 일(M)에 택할 수 있는 과제의 수는 [M <= 과제 마감일] 조건을 만족하는 과제만 해당되기 때문이다. 이 중에 가장 점수가 큰 과제를 수행하면 자연스럽게 점수의 최댓값을 구할 수 있다.

 

예제 1을 예시로 들면

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5
일자 가능한 과제 최적의 과제
6 (6, 5) (6, 5)
5 X X
4 (4, 10), (4, 40), (4, 60) (4, 60)
3 (3, 30), (4, 10), (4, 40) (4, 40)
2 (2, 50), (3, 30), (4, 10) (2, 50)
1 (1, 20), (3, 30), (4, 10) (3, 30)

 

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

1374번 : 강의실  (0) 2023.08.04
10775번 : 공항  (0) 2023.08.03
12904번 : A와 B  (0) 2023.08.02
2212번 : 센서  (0) 2023.08.02
19539번 : 사과나무  (0) 2023.07.31
  • 문제
  • 입력
  • 출력
  • 소스코드
  • 해결방법
'알고리즘/백준' 카테고리의 다른 글
  • 1374번 : 강의실
  • 10775번 : 공항
  • 12904번 : A와 B
  • 2212번 : 센서
코딍코딍
코딍코딍
ㅎ2

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.