본문 바로가기

그리디31

[백준 20115] 에너지 드링크 (C++) https://www.acmicpc.net/problem/20115문제페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다.야근을 마치고 한밤중에 퇴근하니 벌써 새벽 1시. 하지만 주말은 아직 멀었고, 다음 날에도 정시에 출근해야 하는 페인은 오늘도 에너지 드링크를 찾는다.반복되는 야근에 지친 나머지, 평소보다 더 많은 에너지와 피로 회복이 필요했던 페인은 집에 있던 에너지 드링크들을 한 데 합쳐서, 하나의 에너지 드링크로 만들어 한번에 마시려 한다.페인이 에너지 드링크들을 합치는 과정은 다음과 같다.임의의 서로 다른 두 에너지 드링크를 고른다.한쪽 에너지 드링크를 다른 쪽 에너지 드링크에 .. 2025. 1. 10.
[백준 1339] 단어 수학 (C++) https://www.acmicpc.net/problem/1339문제민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 입력첫째 .. 2025. 1. 8.
[백준 31964] 반품 회수 (C++) https://www.acmicpc.net/problem/31964문제아래 그림과 같이 직선 형태의 도로상에 왼쪽부터 오른쪽으로 1번부터 N번까지 번호가 붙어 있는 N개의 집이 있다. i (1 ≤ i ≤ N)번 집의 위치는 Xi(Xi > 0)이다. 택배 회사는 한 대의 트럭을 이용해 N개의 집을 방문하면서 반품되는 물건을 회수하려고 한다. 트럭은 택배 회사가 있는 위치 0에서 시각 0에 출발하고, i번 집은 시각 Ti에 반품할 물건을 내놓는다. 트럭은 1의 속력으로 이동하므로, d만큼의 거리를 이동하는데 d시간이 걸린다. 또한, 트럭은 필요하면 움직이지 않고 제자리에 멈춰서 기다릴 수 있다.트럭은 반품할 물건이 나와있는 집의 위치를 지나면 순식간에 물건을 회수할 수 있다. 즉, 물건을 회수하는 데 소요되.. 2024. 12. 29.
[백준 17503] 맥주 축제 (C++) https://www.acmicpc.net/problem/17503문제내일부터 N일 동안 대구광역시에서 맥주 축제가 열립니다!이 축제에서는 무려 K종류의 맥주를 무료로 제공합니다.축제 주최자는 축제에서 더 많은 참가자들이 다양한 종류의 맥주를 즐겼으면 합니다. 그래서 축제에서 참가자들은 하루에 맥주 1병만 받을 수 있고, 이전에 받았던 종류의 맥주는 다시 받을 수 없습니다.맥주를 정말로 사랑하는 대학생 전씨는 무료 맥주 소식에 신이 났습니다. 전씨는 이 맥주 축제에 참가해 총 N일 동안 맥주 N병을 마시려 합니다.하지만 전씨에게는 큰 고민이 있었습니다. 전씨는 맥주를 사랑하지만, 도수가 높은 맥주를 마시면 기절하는 맥주병이 있습니다. 전씨는 맥주를 마시다 기절하면 늦잠을 자 다음 날 1교시 수업에 결석해.. 2024. 12. 16.
[백준 27277] 장기자랑 (C++) https://www.acmicpc.net/problem/27277문제즐거운 설날을 맞아 부대 장기자랑 행사가 개최된다! 이 행사는 한 번에 한 명씩 순서대로 공연하는 형식으로 진행된다.장기자랑 행사의 총관리자는 공연하는 병사들의 장기자랑 실력을 토대로 행사를 준비하던 중, 아무래도 앞에 공연한 사람이 너무 잘하면 뒤에 공연하는 사람이 부담감을 느껴 본 실력을 발휘하지 못할 것이라는 고민을 하게 되었다. 이에 총관리자는 각 병사의 장기자랑 실력을 순서대로 a1,a2,⋯,an이라고 할 때, 2 ≤ i ≤ N에 대하여 i번째 공연자는 실력을 max(0,ai−ai−1)만큼만 발휘할 수 있을 것이라는 가설을 세웠다. 이때, 가장 먼저 공연하는 병사는 본인의 실력을 그대로 발휘할 수 있다.위 가설에 따라, 총관리.. 2024. 12. 14.
[백준 31845] 카드 교환 (C++) https://www.acmicpc.net/problem/31845문제인하대학교 축제가 열리면, 인천 최대 규모의 카지노인 인하 카지노도 함께 문을 연다. 손님들의 더 많은 유입을 원했던 인하 카지노는 모두가 즐길 수 있는 새로운 카드 게임을 만들었다. 새로운 카드 게임의 진행 방식은 다음과 같다.딜러와 플레이어는 각각 1부터 N까지의 정수가 적힌 카드를 한 장씩 받는다. 딜러는 아무것도 적혀있지 않은 더미 카드 한 장을 추가로 받는다. 그리고 플레이어는 가진 점수가 0인 상태에서 게임을 시작하여 턴을 M회 수행한다. 각 턴은 아래와 같은 순서대로 진행된다.플레이어가 딜러의 패에서 원하는 카드를 하나 가져온다.플레이어의 패에서 같은 값을 가진 카드 쌍이 만들어진 경우, 그 카드 쌍은 패에서 제거된다. 그.. 2024. 12. 9.
[백준 15904] UCPC는 무엇의 약자일까? (C++) 문제UCPC는 '전국 대학생 프로그래밍 대회 동아리 연합 여름 대회'의 줄임말로 알려져있다. 하지만 이 줄임말이 정확히 어떻게 구성되었는지는 아무도 모른다. UCPC 2018을 준비하던 ntopia는 여러 사람들에게 UCPC가 정확히 무엇의 줄임말인지 물어보았지만, 아무도 정확한 답을 제시해주지 못했다. ntopia가 들은 몇 가지 답을 아래에 적어보았다.Union of Computer Programming Contest club contestUnion of Computer Programming contest Club contestUnion of Computer Programming contest club ContestUnion of Collegiate Programming Contest club con.. 2024. 11. 24.
[백준 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.

티스토리툴바