그리디(26)
-
[BOJ 28359] 수열의 가치
https://www.acmicpc.net/problem/28359 28359번: 수열의 가치 첫째 줄에 $N$이 주어진다. $(1 \le N \le 1\,000)$ 둘째 줄에 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le N)$ www.acmicpc.net - 문제 요약 어떤 정수 수열 X의 가치는 다음과 같이 정의된다: X에서 감소하지 않는 부분 수열 P와 증가하지 않는 부분 수열 Q를 임의로 선택했을 때, (P의 모든 원소의 합) + (Q의 모든 원소의 합)의 최댓값 길이가 N인 정수 수열 A가 주어진다. A를 원하는 대로 재배열하여 수열의 가치를 최대화하고 싶다. 재배열하여 만들 수 있는 수열의 가치의 최댓값과 이때의 수열을 찾아보자. ..
2023.07.22 -
[BOJ 28353] 고양이 카페
https://www.acmicpc.net/problem/28353 28353번: 고양이 카페 첫째 줄에 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 5\,000;$ $1 \leq K \leq 10^9)$ 둘째 줄에는 각 고양이의 무게를 의미하는 $N$개의 정수 $w_1, w_2, \dotsm, w_N$이 공백으로 구분되어 주어 www.acmicpc.net - 문제 요약 찬우는 친구들과 고양이 카페에 가려 한다. 고양이 카페에는 N마리의 고양이가 있다. i번째 고양이의 무게는 w_i이다. 찬우와 친구들은 모두 고양이를 사랑하기 때문에 무릎 위에 고양이를 정확히 2마리 데리고 있으면 행복해진다. 하지만 허약한 찬우와 친구들은 데리고 있는 두 고양이의 무게의 합이 K를 넘..
2023.07.20 -
[BOJ 2878] 캔디캔디
https://www.acmicpc.net/problem/2878 2878번: 캔디캔디 첫째 줄에 M(1 ≤ M ≤ 2×109)와 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 친구들이 받고 싶어하는 사탕의 개수가 주어진다. 이 개수는 2×109보다 작으며, 친구들이 받고 싶어하는 www.acmicpc.net - 문제 요약 택희는 M개의 사탕을 N명의 친구들에게 나누어 주려고 한다. 택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다. 만약 받고 싶은 개수만큼 사탕을 받지 못한다면, 그 친구는 분노하게 된다. 놀랍게도 택희는 친구들의 분노를 수치화할 수 있는데, 이것은 못 받는 사탕 개수의 제곱이다. 택희가 받은 사탕의 개수와 친구의 수, 그리고 그 친구들이 받고 싶어..
2023.05.15 -
[BOJ 15998] 카카오머니
https://www.acmicpc.net/problem/15998 15998번: 카카오머니 만약 유효한 최소 충전 단위 M(1 ≤ M ≤ 9 * 1018)이 존재한다면, 첫 번째 줄에 M 을 출력한다. 가능한 값이 여러 가지 있다면, 그중 9 * 1018 이하인 것을 아무거나 하나 출력한다. 존재하지 않는다면 www.acmicpc.net - 문제 요약 카카오페이는 카카오톡을 통해 송금, 결제 등을 할 수 있는 핀테크 서비스이다. 처음에 무지의 카카오머니 잔액은 0원이다. 이 문제에서는 입금 또는 출금할 때 액수가 1원 단위여야 한다는 것 외의 별다른 제약이 없다고 가정하자. 즉, 실제 카카오머니의 제약사항인 잔액 200만 원 이하, 송금은 1일에 50만 원 한도 등은 무시한다. x 원이 입금될 경우, ..
2023.05.12 -
[BOJ 9576] 책 나눠주기
https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net - 문제 요약 백준이는 방 청소를 하면서 필요 없는 N권의 전공 서적을 사람들에게 나눠주려고 한다. 조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미..
2023.05.07 -
[BOJ 4716] 풍선
https://www.acmicpc.net/problem/4716 4716번: 풍선 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 팀의 수 N(1 ≤ N ≤ 1,000)과 방 A와 B에 보관되어있는 풍선의 수 A, B가 주어진다. (0 ≤ A, B ≤ 10,000) 다음 N개 www.acmicpc.net - 문제 요약 전대프연 대회에서 문제를 푼 팀은 풍선을 받게 된다. 풍선은 사람이 직접 달아주기 때문에 자원 봉사자가 필요하다. 풍선은 방 A와 방 B에 보관되어 있다. 대회에 참가한 팀의 수는 총 N개이고, 앉아있는 자리는 서로 다르다. 어떤 팀은 방 A에 가깝고, 어떤 팀은 B에 더 가깝다. 각 팀에게 달아줘야 하는 풍선의 수와 방 A와 B로부터의 거리가 주어진다...
2023.05.07