본문 바로가기

ps139

[백준] 1943 - 동전 분배 https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원 www.acmicpc.net 동전의 가치와 개수가 N개 주어지고, 해당 동전으로 (금액 총 합 / 2)을 만들 수 있는지 판단하는 문제이다. 백트래킹으로 접근할 시에, 최대 O(2^동전의 개수) 만큼 시간복잡도가 걸리기에 다른 방식으로 해결해야 한다. 문제를 잘 보면 입력으로 주어지는 금액의 총 합은 100,000원을 넘지 않는다고 하였다. 그렇다면 0 ~ 100000원이 되는 경우만 판단할 수 있겠다. 즉, .. 2022. 12. 29.
[백준] 24042 - 횡단보도 https://www.acmicpc.net/problem/24042 24042번: 횡단보도 당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, www.acmicpc.net 골드 1까지 되는 문제인지는 잘 모르겠다. 이 문제는 다익스트라로 해결할 수 있는데, 가중치가 동적으로 변경된다. 즉, 주기에 맞지 않게 정점을 방문하면 다음 주기(+m)에 다음 정점을 방문할 수 있다는 뜻이다. 그래서 현재 주기에 갈 수 있는지 없는지를 판단한 후에 -> ((i.second - cost) % m + m) % m 이동하는 시간을 더하면 된다 -> + 1 1. 에서 식을 저렇게 .. 2022. 12. 29.
[백준] 22954 - 그래프 트리 분할 https://www.acmicpc.net/problem/22954 22954번: 그래프 트리 분할 첫 번째 줄에 정점의 개수 $N$, 간선의 개수$M$이 주어진다. ($1 \le N \le 100\,000$, $0 \le M \le 200\,000$) 두 번째 줄부터 $M$줄에 걸쳐서 간선을 나타내는 정수 $u$와 $v$가 주어진다. ($1 \le u, v \le N$, $u www.acmicpc.net 이 문제를 처음 봤을 때 당연히 그래프가 하나가 주어진다고 생각했다. 하지만 몇 번의 WA 끝에 여러 개의 그래프가 주어질 수 있다고 판단했고, 그게 맞았다. 그래서 처음 주어지는 그래프의 수에 따라 구성적으로 설계해 보자. 처음 주어지는 그래프의 수가 3개 이상 이 경우는 이미 3개 이상의 요소들이 .. 2022. 12. 28.
[백준] 13144 - List of Unique Numbers https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 연속한 수열 중, 중복이 없는 수열의 개수를 구하는 문제이다. 문제의 N 제한은 100,000으로 O(N), O(NlogN) 등의 시간 복잡도로 해결해야 한다. 사실 수열의 부분 쿼리를 하는 문제들은 보통 DP 또는 투 포인터, sliding window 등으로 해결 가능하다. 투 포인터로 이 문제를 해결해 보자. 예제 입력 2의 모든 경우를 앞에서부터 구해보자. 1 2 1 2 3 2 3 1 2 3 2 .. 2022. 12. 28.
[백준] 22866 - 탑 보기 https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 원래 건물 높이를 다루는 문제는 스택 하나로 쉽게 풀 수 있다. 하지만, 이 문제는 현재 건물보다 높은 건물 모두(양쪽)를 구해야 하는 문제이다. 따라서 본인은 이 문제를 두 개의 스택을 이용해서 해결했다. 사실상 두 개의 스택이라고 해보았자, 인덱스만 바뀌는 거라서 크게 다를 게 없다. 그래서 왼쪽을 다루는 스택 l만 가지고 풀이를 해보겠다. 문제의 예시를 그림을 그려보자. 이러한 입력이 왼.. 2022. 12. 5.
[백준] 1799 - 비숍 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 이 문제를 처음 풀 때는, 모든 경우의 수를 생각하였다. 이렇게 순수하게 접근할 경우, O(2 ^ 100)으로 10초라는 시간에도 통과하지 못한다. 여기서 비숍의 특징을 생각해보자. 만약 비숍이 체스판의 흑색 위치에 있다면, 체스판의 백색 위치에 갈 수 있는 방법은 없다. 마찬가지로 만약 비숍이 체스판의 백색 위치에 있다면, 체스판의 흑색 위치에 갈 수 있는 방법은 없다. 따라서 비숍은 현재 위치의 색이 .. 2022. 11. 11.
[백준] 1477 - 휴게소 세우기 https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 이 문제를 보자마자 파라메트릭 서치가 떠올랐다. 이분 탐색이라는 카테고리는 왜 필요한지 모르겠지만, 고속도로의 길이 L이 많이 커진다면 이분 탐색이 필요할 것이다. 하지만 100 n >> m >> l; for (int i = 0; i > a[i]; } sort(a, a + n); a[n++] = l; int left = 1, right = a[0]; for (int i = 1; i < n;.. 2022. 11. 11.
[백준] 3079 - 입국심사 https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 파라매트릭 서치로 해결할 수 있다. 그런데 고려해야 할 점이 있다. 문제의 입력 제한에 N과 M을 보면, 단순히 이분 탐색의 시작과 끝을 각각 0, long long limit으로 설정할 수 있다. 하지만 다음과 같은 입력을 고려해보자. N = 100000 M = 1000000000 모든 T_i = 1 그렇다면 mid가 대략 10^17이라고 할 때, mid / T_i가 N(10000.. 2022. 11. 8.
[백준] 13911 - 집 구하기 https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 간략하게 요약하면 임의의 정점에서 서로 다른 두 정점까지의 거리의 최솟값을 구하는 문제이다. 모든 맥도날드와 스타벅스 정점에서 다익스트라를 실행하면 TLE가 나기 때문에 다른 방법을 구사해야 한다. 핵심은 다음과 같다. 맥도날드에 이어진 가상의 정점과, 스타벅스에 이어진 가상의 정점을 생성하고 가중치가 0인 간선으로 연결하는 것이다. 이 예제에.. 2022. 11. 8.

티스토리툴바