greedy(11)
-
[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 1398] 동전 문제
https://www.acmicpc.net/problem/1398 1398번: 동전 문제 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다. www.acmicpc.net - 문제 요약 구사과국은 동전만 사용하고, 동전의 가치는 다음과 같다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000... 즉, 식으로 표현하면 K ≥ 0를 만족하는 모든 K에 대해서, 가치가 10K인 동전과 25×100K인 동전이 있는 것이다. 구사과국에 살고 있는 구사과는 초콜릿을 하나 구매해 5차원 세계로 이사 가려고 한다. 초콜릿의 가격이 주어졌을 때, 이를 구매하기 위해 필요한 ..
2023.05.02 -
[BOJ 19590] 비드맨
https://www.acmicpc.net/problem/19590 19590번: 비드맨 구슬을 엄청 좋아하는 비드맨이 있다. 구슬만 보면 갖고 싶어 하는 비드맨은 오늘도 갖고 싶은 구슬을 발견했다. 그러나 비드맨은 현재 구슬을 너무 많이 갖고 있기 때문에 더 이상 구슬을 가질 www.acmicpc.net - 문제 요약 비드맨은 서로 다른 종류의 구슬 두 개를 부딪히면 서로 깨져 없어진다는 것을 알고 있다. 이 사실을 이용해서 비드맨은 현재 가지고 있는 구슬의 개수를 최소로 하고자 한다. 서로 다른 종류의 구슬 두 개를 부딪혀서 최대한 구슬을 없앤다고 할 때 남게 되는 구슬의 개수는 몇 개인지 구하시오. 첫 번째 줄에는 비드맨이 가지고 있는 구슬의 종류 N이 주어진다. 두 번째 줄부터 N개의 줄에는 x1..
2023.04.21 -
[BOJ 3109] 빵집
https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net - 문제 요약 유명한 제빵사 김원웅은 빵집을 운영 중이다. 원웅이는 지출을 줄이기 위해 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. 원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있으며, 이런 경우에는 파이프를 놓을 수..
2023.04.07 -
[BOJ 21819] Acowdemia
- 문제 요약 소 베시는 컴퓨터 과학에 대한 그녀의 사랑과 언젠가 "베시 박사"가 되는 매력에 이끌려 컴퓨터 과학 박사 과정에 등록했습니다. 한동안 학술 연구에 종사한 그녀는 현재 N개의 논문(1
2023.03.26 -
[BOJ 1226] 국회
https://www.acmicpc.net/problem/1226 1226번: 국회 첫째 줄에 당의 수 N (1 ≤ N ≤ 300), 둘째 줄에 각 당의 의석 수가 주어진다. 각 당의 의석 수는 100,000을 넘지 않는 음이 아닌 정수이다. 당의 번호는 1번부터 N번까지이며, 모든 당의 의석 수의 합 www.acmicpc.net - 문제 요약 국회에는 당이 N개 있고, 각각의 당은 확보한 의석이 있다. 이번에 당끼리 연합을 맺기로 했다. 연합이 유효하려면, 연합에 속한 당의 의석의 합이 전체 의석의 반을 넘어야 한다. 유효한 연합에서 소속된 당 하나를 제거했을 때, 여전히 유효한 연합이라면, 그 연합을 깔끔하지 못한 연합이라고 한다. 유효한 연합 중에서 깔끔하지 못한 연합을 제외한 것을 깔끔한 연합이라..
2023.02.24