본문 바로가기

백준308

[백준 16562] 친구비 (C++) https://www.acmicpc.net/problem/16562문제19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 .. 2025. 1. 11.
[백준 20115] 에너지 드링크 (C++) https://www.acmicpc.net/problem/20115문제페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다.야근을 마치고 한밤중에 퇴근하니 벌써 새벽 1시. 하지만 주말은 아직 멀었고, 다음 날에도 정시에 출근해야 하는 페인은 오늘도 에너지 드링크를 찾는다.반복되는 야근에 지친 나머지, 평소보다 더 많은 에너지와 피로 회복이 필요했던 페인은 집에 있던 에너지 드링크들을 한 데 합쳐서, 하나의 에너지 드링크로 만들어 한번에 마시려 한다.페인이 에너지 드링크들을 합치는 과정은 다음과 같다.임의의 서로 다른 두 에너지 드링크를 고른다.한쪽 에너지 드링크를 다른 쪽 에너지 드링크에 .. 2025. 1. 10.
[백준 28357] 사탕 나눠주기 (C++) https://www.acmicpc.net/problem/28357문제소수전공 수업을 마무리한 찬우는 축하의 의미로 학생들에게 사탕을 나누어 주려 한다. 구체적으로, 기준이 되는 음이 아닌 정수 X를 정한 뒤 최종 점수가 X점을 넘는 학생들에게 점수가 높은 만큼 많은 사탕을 줄 것이다. 즉, X+1점을 받은 학생은 1개, X+2점을 받은 학생은 2개, T(T>X)점을 받은 학생은 T−X개의 사탕을 받게 된다.찬우는 학생들에게 최대한 많은 사탕을 나누어주고 싶기 때문에 기준 점수 X를 가능한 한 낮게 정하려 한다. 하지만, 지금 가지고 있는 돈으로는 사탕을 K개까지만 살 수 있기 때문에 사탕의 총 개수가 K개를 넘으면 안 된다.찬우의 수업은 총 N명이 수강했고, i번째 학생은 Ai점을 받았다. 수강생의 수.. 2025. 1. 9.
[백준 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.
[백준 28075] 스파이 (C++) 문제스파이 민겸이는 이웃 나라와의 평화를 위해 N일간 임무를 수행한다.민겸이는 정보 수집과 감시 2가지 임무를 수행한다. 각 임무는 수족관, 시청, 학교에서 수행할 수 있다. 두 임무는 성격이 크게 다르기 때문에 하루에 한 가지 임무만 수행할 수 있으며, 수족관, 시청, 학교는 멀리 떨어져 있기 때문에 하루에 한 가지 장소에서만 임무를 수행할 수 있다. 또한, 민겸이는 반드시 하루에 최소 하나의 임무를 수행해야 한다. 다시 말해, 민겸이는 하루에 위 표의 6가지 행동 중 하나를 선택하여 할 수 있다.민겸이는 각 장소에서 각 임무를 수행할 때, 임무 완수를 위한 진척도를 얻을 수 있다. 그러나 민겸이는 스파이이기 때문에, 같은 장소에서 오래 근무하면 사람들의 눈에 띄어 얻을 수 있는 진척도가 낮아진다. 민.. 2025. 1. 7.
[백준 13265] 색칠하기 (C++) https://www.acmicpc.net/problem/13265문제어린 토니킴은 색칠공부를 좋아한다.토니킴은 먼저 여러 동그라미와 동그라미 두 개를 연결하는 직선들 만으로 그림을 그리고 (모든 동그라미들 사이에 직선이 있을 필요는 없다), 연결된 두 동그라미는 서로 색이 다르게 되도록 색을 칠하고자 한다.이 그림을 색칠하는데 필요한 최소의 색의 개수를 구하는 문제는 어렵기 때문에 토니킴은 2 가지 색상으로 색칠이 가능한지의 여부만을 알고 싶어한다.동그라미들의 번호와 동그라미들이 서로 연결된 직선에 대한 정보가 주어졌을 때, 이 동그라미들이 2 가지 색상으로 색칠이 가능한지 알아내자. 입력입력의 첫 줄에는 테스트 케이스의 개수 T 가 주어진다.그 다음 줄부터 각 테스트 케이스에 대해 동그라미의 개수 n.. 2025. 1. 6.
[백준 31860] 열심히 일하는 중 (C++) https://www.acmicpc.net/problem/31860문제 송이는 이번 학기에 할 일이 매우 많다. N$N$개의 일 중 어떤 일부터 해야 할지 고민하던 중 송이에게 좋은 아이디어가 떠올랐다! 바로 해야 할 일 각각의 중요도를 산정하고, 중요도가 높은 일부터 하는 것이다. 송이는 하루에 하나의 일만 처리할 수 있으며, 일을 처리한 후 그 일의 중요도는 M$M$만큼 감소한다. 일의 중요도가 K$K$ 이하가 되면 그 일은 완료한 것으로 간주한다. 중요도를 일별로 산정하던 중 송이는 문득 일하면서 본인이 매일 느낄 만족감이 궁금해졌다. 오늘의 만족감은 전날의 만족감을 Y$Y$, 오늘 할 일의 중요도를 P$P$라 할 때 ⌊Y/2⌋+P$\lfloor Y/2 \rfloor+P$와 같다.예를 들면 다음과 .. 2025. 1. 5.
[백준 2624] 동전 바꿔주기 (C++) https://www.acmicpc.net/problem/2624문제명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.20 = 10×2 20 = 10×1 + 5×2 20 = 10×1 + 5×1 + 1×5 20 = 5×3 + 1×5입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의.. 2025. 1. 4.
[백준 11559] Puyo Puyo (C++) https://www.acmicpc.net/problem/11559문제뿌요뿌요의 룰은 다음과 같다.필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지.. 2025. 1. 3.

티스토리툴바