BOJ 14864 : 줄서기 14864번: 줄서기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 학생 수 N (1 ≤ N ≤ 100,000)과 순서쌍의 수 M (0 ≤ M ≤ 1,000,000)이 공백으로 분리되어 주어진다. 일렬로 서 있는 학생들을 순서대로 학생1, 학 www.acmicpc.net i번째 숫자카드보다 작은 숫자카드의 갯수를 c[i]라고 하자. 그렇다면 순서쌍 (x,y)에 따르면 x가 y보다 더 큰 숫자카드이므로 c[x]는 1 증가, c[y] = 1 감소한다. 이를 계속해주면 되고, 같은 수의 숫자카드는 없기 때문에 값이 같게 나올경우 안되는 경우이므로 -1을 출력하면 된다. 코드

BOJ 20192 : 순서 섞기 20192번: 순서 섞기 정수가 저장된 크기 N인 배열 A가 있을 때, ‘순서 섞기’ 연산은 아래와 같이 정의된다. 크기가 N인 배열 B를 이용하여, 배열 A의 좌측 끝 또는 우측 끝에 있는 값 중 하나를 차례로 꺼내어 배열 B www.acmicpc.net 관찰이 조금 까다로운 문제이다. 먼저 문제를 관찰하면 수열을 증감 상태로 나타내면 전환되는 점이 있는데, 이를 순서를 바꿀때 전환되는 점이 한번 섞을때 최대 그 반만큼 감소한다는 거다. 그래서 전환점을 O(N)에 찾으면 된다. 바꾼 횟수는 log2(전환점)으로 계산하면 된다. 코드 djayy035/dj035_PS 코드저장소. Contribute to djayy035/dj035_PS development by creati..

BOJ 2618 : 경찰차 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 아주 왤논 dp. 쫄고 있었는데 의외로 쉬워서 놀랐다. 환상의 듀엣 문제(먼저 보고 오는 걸 추천.)와 비슷한 느낌으로 dp를 해보자. dp[i][j] = i번째 사건을 1번 경찰차가, j번째 사건을 2번 경찰차가 담당할때 최적해. dist(i, j) = i번째 사건과 j번째 사건 사이의 유클리드 거리. nxt = 다음 사건. 이라고 정의한다면 dp[i][nxt] = min(dp[i][j] + dist(j, nxt), dp..

BOJ 11570 : 환상의 듀엣 11570번: 환상의 듀엣 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높 www.acmicpc.net dp로 풀 수 있다. dp[i][j] = i번째 음을 이가, j번째 음을 이가 불렀을때 최적해 A_i = i번째 음을 부를때 비용 nxt = 불러야 할 음 이라고 정의할 때, dp[i][nxt] = min(dp[i][j] + |A_nxt - A_j|, dp[i][nxt]) dp[nxt][j] = min(dp[i][j] + |A_nxt - A_i|, dp[nxt][j]) 코드 djayy035/dj035_PS 코드저장소. Contrib..

16562번: 친구비 (acmicpc.net) 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 친구의 친구들은 모두 친구가 될 수 있다. 그렇다면 우리는 친한 부류끼리 묶어내서 그 부류 중 비용이 가장 최소인 것을 골라 더해주면 된다. 이는 Union-find로 하면 된다. 코드 djayy035/dj035_PS 코드저장소. Contribute to djayy035/dj035_PS development by creating an account on GitHub. gi..

브론즈가 상당히 쉬워서 실버로 넘어왔다. 히힣 1. Cowntagion 전형적인 트리 관련 문제. 감염된 소들이 모두 다른 곳으로 이동할 수 있게 하는 시간은 [log2(d(n)+1)]이다. (이때 d(n)은 n번 노드의 차수를 말하는 것이다.) 이동할 때 1일이 걸리므로, n-1일이 걸린다. 그러므로 답은 ∑[log2(d(n)+1)]+n-1이다. 코드 djayy035/dj035_PS 코드저장소. Contribute to djayy035/dj035_PS development by creating an account on GitHub. github.com 2. Rectangular Pasture (푸는 중) 3. Stuck in a Rut 아...브론즈... (푸는 중)