본문 바로가기
728x90

전체 글587

백준 <Fruit Feast> 백준 알고리즘 11964번 https://www.acmicpc.net/problem/11964 11964번: Fruit Feast Bessie has broken into Farmer John's house again! She has discovered a pile of lemons and a pile of oranges in the kitchen (effectively an unlimited number of each), and she is determined to eat as much as possible. Bessie has a maximum fullness of \(T\) ( www.acmicpc.net 11964번 Bessie는 쌓여있는 레몬과 오렌지를 발견했다. 이 레몬과 오렌지를 최대한 많이.. 2024. 2. 18.
코드트리 <격자 칠하기 2> 격자 칠하기 2 문제 해결 숫자들의 차이인 D를 이진탐색을 활용해 찾았다. binarySearch 함수 start는 0이고, end는 1000000으로 설정했다. 왜냐면 칸에 적힌 숫자가 0과 1000000 사이이기 때문이다. mid를 D라고 생각했을 때, 만약 색칠된 칸이 전체 칸의 반 이상이라면 먼저 Answer을 갱신해주고, 덜 색칠하기 위해 D의 값을 줄여야 한다. 즉, end의 값을 mid-1로 업데이트한다. 만약 색칠된 칸이 전체 칸의 반보다 적다면 더 색칠하기 위해 D의 값을 키워야 한다. 즉, start의 값을 mid+1로 업데이트한다. 이때 색칠된 칸이 전체 칸의 반 이상인 것을 알기 위해 isColored 함수를 사용한다. isColored(int d) 함수 (0, 0) 부터 (N-1,.. 2024. 2. 15.
코드트리 <번호표를 든 N명의 사람> 번호표를 든 N명의 사람 문제 해결 무대에 올리는 수 K를 이진탐색으로 찾아 Tmax를 넘지 않는 K의 최솟값을 찾았다. maxTime 함수를 통해 K가 N일 때 걸리는 시간을 구한다. K가 N일 때는 모든 사람이 무대에 같이 올라가기 때문에 무대에 머무르는 시간이 가장 큰 사람의 시간이 모두 무대에 올라갔다 내려오는데 걸리는 시간(total)이 된다. onStage 함수는 파라미터로 주어진 k를 무대에 올릴 수 있는 최대 수라고 가정하고 모두 무대에 올라갔다 내려오는데 걸리는 시간(total)을 구한다. total을 구하는 것은 우선순위 큐에 무대에서 내려가야 하는 시간을 넣으면서 마지막 사람이 내려오는 시간을 구하면 된다. 처음에 순서대로 k명이 무대에 머무르는 시간을 우선순위 큐에 넣는다. (처음에.. 2024. 2. 15.
백준 2470번 <두 용액> 백준 알고리즘 2470번 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 2470번 많은 종류의 산성 용액과 알칼리성 용액이 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은.. 2024. 1. 11.
백준 1253번 <좋다> 백준 알고리즘 1253번 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 1253번 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 문제 해결 처음에는 이분탐색을 이용해 풀려고 했는데 0때문에 고려해야 할 경우가 많아져서 다른 방법으로 풀 수 있는 방법은 없을까 고민했다. 더보기 좋은 수인지 확인.. 2024. 1. 5.
백준 2589번 <보물섬> 백준 알고리즘 2589번 https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 2589번 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어.. 2023. 12. 31.
728x90

티스토리툴바