본문 바로가기

그리디33

[백준 25947] 선물할인 (C++) https://www.acmicpc.net/problem/25947문제 n개의 선물 가격이 주어졌을 때, b의 예산으로 최대로 많은 선물을 사려고 한다. 이때 최대 a개의 선물에 대해서는 반값 할인을 받을 수 있다고 했을 때 최대로 살 수 있는 선물의 수를 구하는 프로그램을 작성하시오. 단, 한 선물에는 최대 한 번만 반값 할인을 받을 수 있다. 입력입력은 표준입력을 사용한다. 첫 번째 줄에 선물의 개수를 나타내는 양의 정수 n (1 ≤ n ≤ 100000), 예산을 나타내는 양의 정수 b (1≤b≤109), 반값 할인을 받을 수 있는 최대 선물의 수를 나타내는 정수 a (0 ≤ a ≤ n)가 공백을 사이에 두고 차례로 주어진다. 다음 줄에 n개의 선물 가격이 공백을 사이에 두고 주어진다. 선물 가격은 .. 2024. 11. 17.
[백준 23559] 밥 (C++) https://www.acmicpc.net/problem/23559문제제주대 학생회관 식당에는 두 개의 메뉴가 있다. 코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다.준원이는 대면 수업이 시작되는 바람에 이제 남은 학기의 N일동안 매일 학식의 두 메뉴 중 정확히 하나를 골라서 먹어야 한다. N일간의 두 메뉴는 이미 공지되어 있고, 준원이는 이미 모든 날의 각 메뉴가 얼마나 맛있을지 수치를 매겨 두었다.준원이는 N일간 학식에 총 X원 이하를 써야 한다.여러분이 N일간 준원이의 메뉴를 잘 골라서, 고른 메뉴의 맛의 합을 최대화 해주자!입력첫째 줄에는 두 정수 N, X가 주어진다.둘째 줄부터 N개의 줄에, 각 날에 먹을 수 있는 5,000원짜리 메뉴.. 2024. 11. 9.
[백준 1213] 팰린드롬 만들기 (C++) https://www.acmicpc.net/problem/1213문제임한수와 임문빈은 서로 사랑하는 사이이다.임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오. 입력첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다. 출력첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다. 문제 풀이그리디 문.. 2024. 11. 4.
[백준 20300] 서강근육맨 (C++) https://www.acmicpc.net/problem/20300문제로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.헬스장에 있는 N개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 10개의 운동기구가 있을 경우 PT를 5번 받으면 모든.. 2024. 10. 31.
[백준 31589] 포도주 시음 (C++) https://www.acmicpc.net/problem/31589문제산들이는 포도주(와인)를 좋아한다. 그는 마트에서 팔고 있는 N종류의 포도주를 사서 음미하려고 한다. 포도주를 한 병 단위로 사기엔 산들이가 금전적으로 부담이 있기 때문에 그는 작은 용기에 담긴 포도주를 살 것이다. 마트에서 팔고 있는 N종류의 포도주들은 각각 T1, T2, …, TN의 맛을 갖고 있다. 맛의 값이 높은 포도주가 더 맛있는 포도주이다.산들이가 맛있는 포도주를 마시다가 맛없는 포도주를 마시면 그 맛이 감기약 맛을 방불케 하기 때문에 사실상 0의 맛을 느낀다. 하지만 맛없는 포도주를 마시다가 맛있는 포도주를 마시면 그 두 포도주의 맛 차이만큼 맛을 느낀다. 예외적으로 가장 먼저 마시는 포도주의 맛은 그 포도주 본연의 맛 그.. 2024. 10. 7.
[백준 17615] 볼 모으기 (C++) https://www.acmicpc.net/problem/17615 문제빨간색 볼과 파란색 볼이 에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.예를 들어, 처음에 볼이 에서 보인 .. 2024. 9. 21.
[백준 1448] 삼각형 만들기 (C++) https://www.acmicpc.net/problem/1448문제세준이는 N개의 빨대를 가지고 있다. N개의 빨대 중에 3개의 빨대를 선택했을 때, 이 빨대로 삼각형을 만들 수 있다면, 세 변의 길이의 합의 최댓값을 구하고 싶다. 입력첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 작거나 같은 자연수이다. 출력첫째 줄에 삼각형 세 변의 길이의 합의 최댓값을 출력한다. 만약 삼각형을 만들 수 없으면 -1을 출력한다.  문제 풀이그리디 문제. 삼각형의 어느 한 변의 길이가 a라면 나머지 두 변의 길이의 합은 a보다 크다.따라서 정렬 후 가장.. 2024. 9. 16.
[백준 25631] 마트료시카 합치기 (C++) https://www.acmicpc.net/problem/25631 문제마트료시카는 속이 비어있는 인형이다. 성빈이는 𝑁개의 마트료시카를 가지고 있다. 𝑖번째 마트료시카의 크기는 𝑎𝑖이고, 마트료시카 속은 모두 비어있다.성빈이는 남아 있는 마트료시카 중에서 𝑖번째와 𝑗번째(𝑖≠𝑗)마트료시카를 고른 뒤에 𝑖번째 마트료시카를 𝑗번째 마트료시카 속에 넣을 수 있다. 단, 𝑗번째 마트료시카의 속이 비어있어야 하고, 𝑖번째 마트료시카보다 𝑗번째 마트료시카가 더 커야 한다. 합친 후에는 남아 있는 마트료시카의 개수가 한 개 줄어든다.성빈이는 마트료시카를 최대한 합쳐서 정리하려고 한다. 성빈이가 마트료시카를 잘 합친다면 남아 있는 마트료시카의 최소 개수는 얼마일까? 입력첫째 줄에 마트료시카의 .. 2024. 9. 4.
[백준 11497] 통나무 건너뛰기 (C++) 문제남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9.. 2024. 9. 3.

티스토리툴바