본문 바로가기

그리디

 (15)
[백준 / BOJ] 17615 볼 모으기 문제 출처 : https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 빨간색과 파란색으로 이루어진 N개의 연속된 공이 주어진다. 자신의 옆에 다른색의 공이 있다면, 바로 옆에있는 다른색의 공과 같은 색으로 이루어진 공의 집단을 한번에 뛰어넘을수있을때, 최소한의 이동횟수로 같은색 공끼리 모으는 문제다. 단, 공은 처음으로 움직인 공과 같은색의 공만 조작할 수 있다. 풀이 그리디 문제였다. N이 500,000이라서 어려워 보이..
[백준 / BOJ] 12904 A와 B 문제 출처 : https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문자 'A'와 'B'가 주어진다. 두 문자를 아래와 같은 규칙으로 연결해 문자열 T를 만든다. 1. 문자열 뒤에 A를 붙인다. 2. 문자열 을 뒤집고 뒤에 B를 붙인다. 이때, 문자열 S를 이용해 문자열 T를 만들 수 있는지 알아내는 프로그램을 만드는 문제다. 풀이 아이디어 문제다. 문자열 S를 이용해 문자열 T를 만들려면, 매 선택마다 2가지 ..
[백준 / BOJ] 21319 챔피언(Easy) 문제 출처 : https://www.acmicpc.net/problem/21319 21319번: 챔피언 (Easy) 1번 선수는 어떻게 해도 챔피언이 될 수 없다. 2번 선수는 어떻게 해도 챔피언이 될 수 없다. 3번 선수는 (2, 3), (1, 3), (3, 4) 순서대로 격투가 일어나면 챔피언이 될 수 있다. 4번 선수는 (3, 4), (2, 4), www.acmicpc.net N명의 선수가 비 내림차순으로 주어진다. 각 선수는 자신의 양쪽선수와 경기를 하며 파워가 더 쌘 선수가 승리한다. 승리시 자신의 파워가 +1 증가하며, 패배한 선수의 양쪽 선수와 연결된다. 위 과정을 반복후, 경기장에 혼자 남아있을때, 그 선수를 챔피언 이라고 한다. 이때, 챔피언이 될 가능성이 있는 선수를 모두 구하는 문제다..
[백준 / BOJ] 19644 좀비 떼가 기관총 진지에도 오다니 문제 출처 : https://www.acmicpc.net/problem/19644 19644번: 좀비 떼가 기관총 진지에도 오다니 킬로와 헥토는 좀비 떼로부터 탄약고를 사수하는 데에 성공했다. 포상 휴가나 조기 전역을 기대했으나 좀비 사태로 인해 계엄령이 선포되면서 오히려 전역이 연기되고 기관총 진지에 배치되었 www.acmicpc.net 기관총 진지에 좀비떼가 다가오고 있다. 킬로와 헥토는 기관총과 지뢰를 이용해 좀비를 막아야한다. 기관총은, L의 사거리에 있는 좀비를 모두 K데미지로 공격한다. 지뢰는 1M사거리에 있는 좀비를 제압한다. 이때, 킬로와 헥토가 좀비 떼에게서 살아남을수있을지 구하는 문제다. 풀이 그리디, 투포인터 문제였다. 좀비의 수(진지의 거리)와 유효사거리가 3*10^6 이므로 시뮬레..
[백준 / BOJ] 20921 그렇고 그런 사이 문제 출처 : https://www.acmicpc.net/problem/20921 20921번: 그렇고 그런 사이 정수 $N$, $K$가 주어진다. ($2 \leq N \leq 4\,242$, $0 \leq K \leq \frac{N(N-1)}{2}$) www.acmicpc.net 환주는 두명을 그렇고 그런 사이로 만드는데 전문가이다. 그렇고 그런 사이가 될려면, 다음 조건을 만족해야한다. (P(i)가 갖고있는 숫자가 P(i+a)보다 커야함) (단, a>0) 환주의 친구의수 N, 그렇고 그런 사이로 만들어야하는 쌍의수 K가 주어졌을때, 그렇고 그런 사이를 만드는 경우를 출력하는 문제다. 풀이 재밌는..? 문제였다. 문제를 처음 봤을때는 감이 잘 안잡혔는데,(dp라고 예상했었음) 문제의 예제를 직접 해보니..
[백준 / BOJ] 1092 배 (Java) 문제 출처 : https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 크래인의 갯수 N, 화물박스의 갯수 M이 주어진다. (1
[백준 / BOJ] 1114 통나무 자르기 문제 출처 : https://www.acmicpc.net/problem/1114 1114번: 통나무 자르기 첫째 줄에 L, K와 C가 주어진다. L은1,000,000,000보다 작거나 같은 자연수이고, K는 통나무를 자를 수 있는 위치의 개수이다. K와 C는 10,000보다 작거나 같은 자연수이다. 둘째 줄에 통나무를 자를 수 www.acmicpc.net 길이 L인 통나무가 주어지고, 이 통나무를 자를수있는 위치가 K개 주어진다. (통나무는 입력된 위치에서만 자를수 있다.) 통나무를 자를수있는 횟수 C가 주어졌을때, 통나무를 적절히 잘라 통나무의 가장 작은 길이가 최대가 되며, 이때 가장 먼저 잘라야하는 인덱스를 구하는 프로그램을 만드는 문제다. 풀이 결정문제 패턴으로 자주 나오는 문제다. 자를수있는 위..
[백준 / BOJ] 1135 뉴스 전하기 문제 출처 : https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 민식이는 회사의 매니저이다. 민식이는 회사의 뉴스를 모든 직원들에게 전하려고한다. 회사의 모든 직원들은 정확히 한명의 선임이 있으며, 자신은 자신의 선임이 아니다. 모든 직원들은 모두 민식이의 간접,직접적인 부하이다. 모든 사람은 자신의 직속부하에게만 뉴스를 전달할수있고, 이때, 1분의 시간이 걸린다. 모든 직원이 뉴스를 전달받는 최소시간을 구하는 문제다. 풀이 그리디로 풀은 문제다. 직..

티스토리툴바