https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 1. Logic 범위가 10억이기 때문에 이분탐색을 사용하여 풀이했다. 처음 승률은 y * 100 / 2이고 이분탐색으로 이긴 횟수를 바꿔가면서 카운팅 할 때는 (y + mid) * 100 / (x + mid)이다. mid를 바꾸면서 승률이 변경되지 않으면 start를 mid로 올려 게임 수를 증가시키면서 처음 변경되는 end값을 찾아주면 된다. 승률을 구할 때 100을 곱해주기 때문에 i..
이분탐색
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 1. Logic 다리가 버틸 수 있는 무게가 10억까지이기 때문에 택배의 무게를 이분탐색으로 찾아준다. 이분탐색의 Check함수는 택배의 무게인 mid보다 각 경로가 버틸 수 있는 무게가 크거나 같을 때만 통과시켜 입력받은 출발지에서 시작하여 도착지에 도달할 수 있으면 택배의 무게를 늘리고 도착하지 못하면 택배의 무게를 줄이면서 적절한 택..
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. Logic 이 문제에서 mid값은 공유기와 공유기 사이의 거리를 뜻한다. 이분탐색으로 공유기와 공유기 사이의 거리를 구한 후 wifi[0]~wifi[n-1]까지 탐색하며 공유기간의 사이가 mid보다 큰거나 같을 때를 count해주며 count가 공유기 설치대수 m보다 크거나 같으면 start를 mid로 옮겨, 작으면 end를 mid로 옮겨 ..
https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 1. Logic 이 문제에서는 이분탐색으로 찾으려는 mid값이 무엇인지를 정하는게 중요하다고 생각한다. 내가 정한 mid값은 블루레이의 길이이다. 강의 영상의 순서대로 블루레이에 넣어야되기 때문에 이분탐색의 check()함수는 블루레이에 순서대로 영상이 들어가는지 판단해주면 된다. 우리가 찾는 mid값은 가능한 값들중에 최솟값이기 때문에 가능한 mid값의 구간은 FFFF[FT]TTTT가 된다. 그중 가능..
https://www.acmicpc.net/problem/17124 17124번: 두 개의 배열 정수 배열 A 와 B가 있다. A는 총 n개의 서로 다른 양의 정수를 포함하고 B는 총 m개의 서로 다른 양의 정수를 포함한다. A, B를 이용해서 길이가 n인 새로운 배열 C를 만들어보자. C[i] 는 배열 B에 있 www.acmicpc.net 1. Logic 로직을 보면 a배열, b배열을 입력받는다. b배열을 오름차순으로 정리한다. a[0]~a[n-1]까지 차례로 이분탐색을 해서 b[start] target 인 값을 구한후 target-b[start], b[end]-target의 절댓값 중 더 작은 값을 선택해서 더해준다. 출력한다. 2. Code #include #include #include #incl..
https://www.acmicpc.net/problem/13702 13702번: 이상한 술집 프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다. 즉 한 번 주문에 막걸리 용 www.acmicpc.net 1. Logic 막걸리 를 최대한 많이 따를 수 있는 만큼 따르고 나머지는 버린다고 했으니 우리는 K잔을 만들 수 있는 최대 값을 찾아야 한다. 우리가 탐색하는 부분에 대해서 정답은 TTT[TF]FFF 중간 대괄호부분에서 정답이 결정된다. 우리가 구해야 하는 값은 가능한 수들중에서 최댓값이기 때문에 left를 반환하면 된다. 2. Code #include #include #include using ..
https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 1. Logic 이 문제는 unordered_map을 활용한 풀이, 이분탐색을 활용한 풀이 총 두가지 방법으로 풀이 가능하다. 2. Code 해시 맵 풀이 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while(t--) ..
https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 1. Logic 값이 참이 되는 구간을 살펴보면 정답 mid를 기준으로 0~left까지는 false, right~n까지는 true이다. 여기서는 참이 되는 값중 최솟값을 구해야 하기 때문에 right를 반환해 주면 된다. 2. Code #include #include using namespace std; int n, m; vector input; int binarySearch() { int start..
https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 1. Logic 두개의 수를 먼저 골라 합을 만들어 놓고 나머지 한개의 수를 골라 0이 되는 수를 카운트 하면 된다. 이 문제에서는 중복되는 수가 나올 수도 있기 때문에 원하는 수가 먼저 나오는 index(lower bound) 원하는 수가 나오는 가장 마지막 index(upper bound) 두개를 구해 빼주어 갯수만큼 구해줬다. 밑의 코드에서 tempSum에 -를 붙혀준 이유는 우리는 a+b+c=0..
https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄 www.acmicpc.net 1. Logic 처음에 이 문제를 보고 0~L까지 거리를 구한 값을 우선순위 큐에 넣은 다음 큰 숫자부터 2로 나눠서 m만큼 반복하면 쉽게 풀릴 것 같다고 생각했다. 하지만 여기에는 반례가 있었다. 만약 테스트 케이스가 0 2 100 다음과 같이 주어졌을때를 가정해 보면 먼저 답은 33이 나와야한다. 우선순위 큐에는 0~100까지 100이 들어가있을 것이다. 우선순위 큐로 항상 2로 ..
