본문 바로가기

이분탐색19

[백준 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.
[백준 1208] 부분수열의 합 2 (C++) https://www.acmicpc.net/problem/1208문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 문제 풀이이분탐색 문제. N이 최대 40개이므로 그대로 모든 가능한 경우의 수를 구하면 시간초과가 발생한다. 수열을 2개로 나누어 각 수열에서의 가능한 수를 구한다.사이즈가 N/2인 배열과 나머지.. 2024. 11. 19.
[백준 2428] 표절 (C++) https://www.acmicpc.net/problem/2428문제세계적인 석유 재벌 "규현 조 압둘 티크리티 안드레스 후세인 리오넬 솔레르 살라 마리우 두스 산투스 펠리스 빈 자이드 술탄 친나왓 뱅거 7세"는 1등 상품으로 페라리를 걸고 프로그래밍 대회를 개최했다. 이 대회의 참석자는 총 N명이고 각각 솔루션 파일 1개를 제출했다. 이 솔루션 파일을 F1, F2, ..., Fn이라고 한다.채점 결과를 발표하기 전에, 남의 것을 배낀 사람이 있는지 찾아내려고 한다. 이 대회의 주최측은 두 파일을 비교해서 너무 비슷한지 아닌지 판별하는 프로그램이 있다.하지만, 제출한 파일의 개수가 너무 많아서, 모든 쌍을 검사한다면, 2012년 지구가 멸망할 때 까지도 검사를 해야할 판이다. 따라서, 파일 크기가 너무 .. 2024. 11. 18.
[백준 3020] 개똥벌레 (C++) https://www.acmicpc.net/problem/3020 문제개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림) 이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다) 하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥.. 2024. 10. 17.
[백준 3079] 입국심사 (C++) https://www.acmicpc.net/problem/3079문제상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다.. 2024. 9. 20.
[백준 3649] 로봇 프로젝트 (C++) https://www.acmicpc.net/problem/3649문제상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다.구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다.지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 모두 정확하게 재고 돌아왔다. 구멍을 완벽하게 막을 수 있는 두 조각을 구하는 프로그램을 작성하시오. 입력입력은 여러 개의 테스트 케이스로 이루어져 있다.각 테스트 케이스의 첫째 줄에는 구멍의 너.. 2024. 8. 22.
[백준 1072] 게임 (C++) 문제 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.게임 기록은 다음과 같이 생겼다.게임 횟수 : X이긴 게임 : Y (Z%)Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=.. 2024. 7. 26.
[백준 29717] 슬라임 잡고 레벨 업! (C++) https://www.acmicpc.net/problem/29717문제오늘은 많은 사람이 기대하던 《실브 스토리》게임이 출시되는 날이다!《실브 스토리》는 MMORPG 장르 게임으로, 몬스터를 잡아 경험치를 모으고 레벨 업을 할 수 있으며, 레벨 업에 필요한 경험치를 넘을 때마다 그에 필요한 경험치만 소진하고 남은 경험치를 그대로 보유한다. 하지만 일반 게임들과 다르게 특이한 점이 두 가지 있다.첫 번째는 게임에 존재하는 몬스터가 슬라임뿐이라는 것이다. 슬라임을 처치했을 때 주는 경험치 또한 특이한데, 유저가 지금까지 처치한 슬라임 수를 𝑥라 할 때, 새로운 슬라임을 처치하면 𝑥+1 만큼의 경험치를 얻게 된다.두 번째는 레벨 업에 필요한 경험치의 증가 방식이다. 현재 레벨에서 레벨 업에 필요한 경험치가.. 2024. 7. 21.
[백준 7453] 합이 0인 네 정수 (C++) https://www.acmicpc.net/problem/7453문제정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. 출력합이 0이 되는 쌍의 개수를 출력한다. 문제 풀이MITM 알고리즘과 투포인터를 같이 사용하는 문제.A, B, C, D 4개 배열을 모든 A+B를 저장하는 벡터 v1, 모든 C+D를 저장하는 벡터 v2 2개로 만들어 시간 복잡도를 줄인다. 벡터를 사용해 .. 2024. 7. 10.

티스토리툴바