본문 바로가기

분류 전체보기172

BOJ 3151 - 합이 0 3151번: 합이 0 (acmicpc.net) 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 접근 방법 3개의 수의 합이 0이 되는 조합을 모두 찾는 문제이다. 2문제를 미리 다 더한 후, 마지막 하나를 이분탐색으로 구하는 문제이다. 이 문제를 처음할 때 실수한 부분이 중복되는 값을 고려하지 않은것이다. 만약, 8 -10 5 5 5 5 5 5 5 다음 케이스가 올 경우, 5를 모두 개별 취급을 해야하므로 21이 되어야 한다. 그러나, 이분탐색의 경우 중복을 처리하는게 쉽지 않기 때문에 lower_bound와 up.. 2024. 4. 17.
BOJ 14921 - 용액 합성하기 14921번: 용액 합성하기 (acmicpc.net) 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 접근방법 용액을 무조건 두 개씩 섞어서 0에 가깝게 만드는 문제이다. 전형적인 투포인터 문제다. 포인터를 두 개만들고(a, b), a는 0부터, b는 끝부터 내려온다. 만약, 두 포인터의 용액의 합이 0보다 작으면 용액의 합을 더 크게해야하기 때문에 a++. 반대로, 용액의 합이 작으면 용액의 값을 줄여야 하기 때문에 b--를 한다. 그리고 매번 용액의 합이 0에 최대한 가까운 합을.. 2024. 4. 16.
BOJ 18869 - 멀티버스 II 18869번: 멀티버스 Ⅱ (acmicpc.net) 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 1차 시도 처음에 각 우주에서 행성 2개씩 비교한 후, 각 위치에 대응하는 비교한 값을 다 더해서 그 갯수로 균등한 우주의 쌍을 구했다. 이 방법은 행성이 4개 이상일 때는 작동하지 않아서 바로 포기했다. 접근방법 정렬 각 행성의 인덱스를 저장한 후, 행성의 크기로 Sort를 하게 되면 각 우주에서 행성들의 인덱스 순서는 똑같아진다. 만약 이 행성의 인덱스가 다르면 균등한 우주가 아니다. 여기에 예외가 있.. 2024. 4. 15.
BOJ 2295 - 세 수의 합 2295번: 세 수의 합 (acmicpc.net) 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 접근 방법 백트래킹, 브루트포스말고는 어떻게 풀어야할지 감이 안잡혔다. 그래서 결국 알고리즘 분류를 봤다... 이 문제에서 어떻게하면 이분탐색으로 풀수있을까 많이 생각해보았다. 무엇을 기준으로 대소비교를 할 것인가? 처음엔 원소의 인덱스를 기준으로 생각해보려고 했지만, 해당 원소의 더한 값을 구하려면 이전 원소들을 모두 3개씩 더해야 한다. 그리고 무엇을 기준으로 .. 2024. 4. 13.
BOJ 16401 - 과자 나눠주기 16401번: 과자 나눠주기 (acmicpc.net) 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 접근 방법 가장 길게 과자를 N명에게 나눠주는 문제이다. 이때 핵심이 과자를 부러뜨리면 다시 합칠 수 없다는 것이다. 예제 1을 보자. 1 2 3 4 5 6 7 8 9 10에서 3명에게 가장 긴 과자를 주려면 8 , 9 , 10을 선택하여 9와 10을 각각 1, 2 만큼 부러뜨려 8로 맞춰 주면된다. 예제 2번의 경우 한 번더.. 2024. 4. 13.
BOJ 2252 - 줄 세우기 2252번: 줄 세우기 (acmicpc.net) 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 접근방법 이번 문제는 위상정렬 문제라는 것을 사전에 알고 풀었다. 왜 위상정렬로 풀어야할지 생각해봤다. 총 N명의 학생들 중 임의의 두 학생 A와 B의 키만 비교하였다. 그리고 이렇게 잰 키를 통해 줄을 세운다. 이는 A와 B를 정점으로 생각할 때, A와 B는 단방향 간선을 가진 그래프가 된다. 이를 통해, 위상정렬하여 각 정점들의 순서를 정할 수 있기 때문에 위상정렬을 .. 2024. 4. 6.

티스토리툴바