본문 바로가기

그리디38

[백준 32630] Ai X Aj 문제크기가 N인 배열이 주어진다. 이 배열에 다음과 같은 연산을 최대 한 번 적용할 수 있다.배열에서 두 원소 Ai와 Aj를 선택한다. (i≠j)선택한 두 원소를 모두 Ai×Aj로 바꾼다.연산을 최대 한 번 적용하였을 때 배열의 합의 최댓값을 구해보자.입력첫 번째 줄에 배열의 크기 N이 주어진다. (2≤N≤2×105)두 번째 줄에 배열의 원소들인 N개의 정수 A1,A2,…,AN이 공백으로 구분되어 주어진다. (−109 ≤ Ai ≤ 109) 출력배열의 합의 최댓값을 출력한다. 문제 풀이그리디 문제. 두 수를 곱했을 때 이득이 되려면 음수 * 음수거나 양수* 양수여야 한다. 음수* 음수인 경우라면 가장 작은 수 두 개를 써야 가장 큰 값을 얻을 수 있고, 양수* 양수라면 가장 큰 수 두 개를 써야 가장 큰 .. 2025. 4. 25.
[백준 29615] 알파빌과 베타빌 (C++) https://www.acmicpc.net/problem/29615문제민규와 친구들은 바로 옆에 붙어있는 두 빌라, 알파빌과 베타빌에 살고 있다. 이 두 빌라 중 알파빌은 싼값에 좋은 빌라라서 너무 인기가 많아 입주하려는 사람들이 줄을 선다. 민규의 친구들 역시 대기 번호를 받아 알파빌의 대기 명단에 적혀있다. 알파빌 입주에 실패한 친구들은 어쩔 수 없이 조금 더 비싼 베타빌에 들어가게 될 것이다. 이를 안타까워한 민규는 더 많은 친구를 알파빌에 입주시키기 위해 집주인 몰래 대기 명단을 바꾸려고 한다.대기 명단에는 입주하려는 사람들의 대기 번호가 입주하는 순서대로 왼쪽에서 오른쪽으로 적혀 있으며, 대기 번호는 1번부터 N번까지의 서로 다른 정수이다.민규는 한 번 명단을 바꿀 때 번호 두 개를 선택해서 서.. 2025. 3. 22.
[백준 30701] 돌아온 똥게임 (C++) https://www.acmicpc.net/problem/30701문제유튜브에서 똥게임 광고를 지나치게 많이 본 근호는 본인이 직접 똥게임을 설치해서 하기로 했다.처음에 근호는 D의 전투력을 가지고 시작한다. 근호 앞에는 N개의 방이 있는데, 각 방에는 몬스터 또는 장비가 있으며 i(1 ≤ i ≤ N)번째 방에 있는 몬스터 또는 장비는 전투력 Xi를 가진다.근호는 매번 아직 돌파하지 않은 방 중 어떤 방에 먼저 들어갈지 자유롭게 정할 수 있으며, 들어간 방에 있는 내용물에 따라 다음과 같이 행동한다.몬스터가 있는 경우: 근호의 전투력이 몬스터의 전투력보다 크면 몬스터를 쓰러뜨릴 수 있으며, 이후 근호의 전투력에 몬스터의 전투력이 더해진다. 근호의 전투력이 몬스터의 전투력보다 작거나 같을 경우 근호는 패배.. 2025. 2. 26.
[백준 26070] 곰곰이와 학식 (C++) https://www.acmicpc.net/problem/26070문제지금 곰곰대학교 학생식당에는 시험기간에 밤을 새, 굶주려 있는 곰곰이들이 기다리고 있다.정확히는 치킨을 먹고 싶은 곰곰이가 A마리, 피자를 먹고 싶은 곰곰이가 B마리, 햄버거를 먹고 싶은 곰곰이가 C마리 있다.총총선배는 사비를 털어 곰곰이들에게 맛있는 밥을 사주려 한다!총총선배는 학생식당에서 사용할 수 있는 치킨 식권 X장, 피자 식권 Y장, 햄버거 식권 Z장을 가지고 있다. 식권 한장을 내면, 해당 음식 1인분으로 교환받을 수 있다.또, 식당에서는 치킨 식권 3장을 피자 식권 1장으로, 피자 식권 3장을 햄버거 식권 1장으로, 햄버거 식권 3장을 치킨 식권 1장으로 교환해주는 이벤트도 하고 있다.곰곰이들을 최대한 배불리 먹이고 싶은 .. 2025. 2. 22.
[백준 1900] 레슬러 (C++) https://www.acmicpc.net/problem/1900문제옛날에 레슬링을 무척 좋아하는 동호라는 국왕이 살았다. 그 당시 레슬링 선수들은 초자연적인 힘을 가졌다. 경기에 이기기 위해서 레슬링 선수는 자신의 힘뿐만 아니라 경기할 때 착용하는 마술 링에도 의존한다. 마술 링은 레슬링 선수로 하여금 상대 선수의 힘에 비례하는 힘을 추가로 얻을 수 있게 해준다.레슬링 선수의 힘과 마술 링의 힘은 모두 양의 정수이다. 선수 A가 선수 B와 경기할 때, A의 ‘경기력’은 ‘A의 힘’ + ‘B의 힘’ * ‘A가 착용하고 있는 마술 링의 힘’이다. 경기에서는 경기력이 높은 선수가 이긴다.예를 들어, 선수 A의 힘이 10이고 착용하고 있는 마술 링의 힘은 3이라고 하고, 선수 B의 힘은 18이고 착용하고 있는.. 2025. 2. 10.
[백준 20413] MVP 다이아몬드 (Easy) (C++) https://www.acmicpc.net/problem/20413문제입력 제한 외 난이도에 따른 문제의 차이는 없다.상민이는 게임 단풍잎이야기에 과금을 즐겨 한다. 단풍잎이야기에는 과금액에 따라 혜택을 제공하는 'MVP 등급'이 존재한다.MVP 등급은 브론즈(B), 실버(S), 골드(G), 플래티넘(P), 다이아몬드(D)로 총 다섯 등급이 있으며, 현재 달과 지난달, 즉 현재 달을 포함한 최근 2개월간의 과금액으로 결정된다.단, 단풍잎이야기에는 과도한 과금을 막기 위해 '최대 과금 한도'가 있어 한 달에 최대 다이아몬드 등급 기준액 까지만 과금할 수 있으며, 만원 단위로만 과금이 가능하다.MVP 등급은 해당 달이 끝날 때 계산되어 책정된다. 예를 들어 아래의 표와 같은 등급 기준액을 따르고 1월에 게임.. 2025. 1. 15.
[백준 17828] 문자열 화폐 (C++) https://www.acmicpc.net/problem/17828문제작년에 소수나라에 다녀온 하나는, 올해는 문자열나라로 관광을 가려고 한다. 문자열나라에서는 특이하게 알파벳 대문자로 구성된 문자열을 화폐로 사용한다.문자열나라에서 'A'는 1의 가치, 'B'는 2의 가치, ..., 'Z'는 26의 가치를 가지고 있으며, 이 알파벳들을 붙여 화폐로 쓰일 문자열을 만든다. 예를 들어, "HONGIK"의 가치는 8 + 15 + 14 + 7 + 9 + 11 = 64가 된다.소수나라에서 특이한 화폐 때문에 큰 스트레스를 받았던 하나는, 이번에는 정확한 소비 계획을 세워 미리 문자열 화폐로 돈을 환전해가려고 한다. 하나가 가져갈 문자열은 딱 하나이며, 길이는 N이고, 가치는 X여야 한다. 그리고 물론 알파벳 대문.. 2025. 1. 13.
[백준 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.

티스토리툴바