https://www.acmicpc.net/problem/27973 27973번: 지연 평가 지연이는 자신이 가진 배열 $S$의 상태를 평가하려고 한다. 처음에 $S$에는 $1$부터 $1 \, 234 \, 567 \, 890 \, 123$까지의 모든 정수가 $1$개씩 들어 있다. 지연이를 도와 다음 명령을 수행하는 프로그램을 www.acmicpc.net 문제의 조건을 읽어봅시다. 1. 1 ~ 1,234,567,890,123 까지의 정수들이 들어간 집합 S가 있음 2. 쿼리 종류에는 모든 원소들에 대해서 특정 값만큼 더하거나 곱하는게 있음 2-1. 단 곱할때는 항상 양의 정수랑 같이 곱하도록 값이 주어짐 3. 또한 작은 원소부터 차례대로 몇 개를 제거하라는 쿼리도 주어짐 4. 쿼리 중에서 출력하라는 쿼리가..

[백준] https://www.acmicpc.net/problem/23630 23630번: 가장 긴 부분 수열 구하기 $N$개의 자연수로 이루어진 수열 $A = \{A_1, A_2, …, A_N\}$가 주어진다. 다음의 조건을 모두 만족하는 $A$의 부분 수열 $\{A_{i_1}, A_{i_2}, ..., A_{i_m}\}$ 중 가장 긴 수열의 길이를 출력하라. $A_{i_1} ~\&~ A_{i www.acmicpc.net 일단 문제의 조건은 문제 자체에도 적혀있지만 풀어서 적으면 아래와 같습니다. 1. 부분 수열의 원소들을 전부 bitwise AND를 했을 때 0이 되면 안됨 2. 부분 수열은 원래 수열에서 위치를 바꾸지 않고 유지해야 합니다. 또한, 동일한 위치의 원소를 여러번 사용하는 것도 불가능 ..

https://www.acmicpc.net/problem/3997 3997번: 하이퍼드롬 첫 번쨰 예제의 경우에 6개의 하이퍼드롬이 있다. - (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3). 두 번째 예제의 경우에는 12개가 있다. - (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (1, 3), (3, 5), (5, 7), (2, 6) www.acmicpc.net 문제를 읽어보면 조건들은 아래와 같습니다. 1. 대소문자 알파벳으로 이루어진 문자열이 주어짐 2. 문자열의 알파벳들을 적절히 바꿔서 팰린드롬을 만들 수 있다면 하이퍼드롬이라고 함 3. 그러면 문자열이 주어졌을 때, 연속된 부분 문자열들 중에서 하이퍼드롬인..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 읽어보면 이 문제의 조건은 아래와 같습니다. 1. 숫자들이 순서대로 주어질때, 중앙값을 계속 출력 2. 짝수개가 있으면 좀 더 작은 걸 선택 꽤나 조건이 간단하고 명확합니다. 이 문제를 처음 보았을 때 저는 매우매우 비슷한 문제를 푼 이력이 있어서 쉽게 결론에 도달하였습니다. 바로, Priority Queue를 두 개를 사용하는 방법입니다. Priority Queue가 왜 갑자기 ..

https://www.acmicpc.net/problem/22345 22345번: 누적 거리 KOI 나라는 수직선 위에 놓인 N개의 마을로 구성되어 있다. 이 중 i (1 ≤ i ≤ N)번째 마을은 xi 위치에 놓여 있으며 ai명이 거주 중이다. 또한 서로 다른 두 마을이 같은 위치에 놓인 경우는 없다. KOI www.acmicpc.net 문제를 읽어보면 조건은 아래와 같습니다. 1. x축 좌표상에 N개의 점이 주어져 있으며 각 점에는 가중치가 존재함 2. 그러면 Q개의 쿼리에서 x축 좌표가 하나 주어졌을 때, 각 점에서의 (거리 * 해당 점의 가중치)를 모두 더한 값을 구해야 함 저는 이 문제보고 처음에는 세그먼트 트리를 활용하는 문제인가 싶었습니다. 왜냐하면, N과 Q의 범위를 보았을 때, 결국에는 ..

https://www.acmicpc.net/problem/28296 28296번: 물류창고 UCPC시에는 $N$개의 물류창고가 있으며, $K$개의 회사가 각 물류창고를 소유하고 있다. 물류창고에는 $1$번부터 $N$번까지 차례대로 번호가 붙어있으며, 회사 또한 $1$번부터 $K$번까지 차례대로 번호 www.acmicpc.net 문제를 읽어보면, 문제의 조건들은 아래와 같습니다. 1. N개의 창고들이 있으며 창고 쌍에 대해서 잇는 간선들도 존재함 2. 간선들은 두 창고 쌍에 대해서 배송 상한선이라는 cost도 가지고 있음 3. 각 창고는 K개의 회사 중 하나에 속해있으며, 창고와 창고간의 배송 상한선은 이동 경로중의 배송 상한선이 제일 작은 간선의 배송 상한선이 됨 4. 여러 경로가 있으면 그 중 배송 상..