본문 바로가기

분류 전체보기93

Priority Queue 개요 Entry를 담는 ADT로, Entry는 보통 key를 우선순위로 하는 { key, value } 쌍이다. 우선순위에 따라 정렬되는 Queue로, Entry 간 Total order relation이 성립한다. Priority Queue 대표적인 operation은 insert, removeMin이 있고, 추가로 min, size, empty 등을 지원할 수 있다. List-based 구현으로 sorted list를 이용하는 방법과 unsorted list를 이용하는 방법이 있다. Total order relation 전순서라고 하며, Reflexive property ( x ≤ x ) Antisymmetric property ( x ≤ y and y ≤ x then x = y ) Transitiv.. 2020. 12. 3.
Educational Codeforces Round 99 (Rated for Div. 2) ABCD import sys input = sys.stdin.readline for TEST in range(int(input())): print(len(input().rstrip())) A - Strange Functions A번에 이렇게 큰 수를 다루는 문제가 나올 리 없기 때문에 당당하게 길이를 출력하였다. #include using namespace std; typedef long long ll; ll dp[2000001]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); set s; for (int i = 1; i TEST; while (TEST--) { int n; cin >> n; cout TEST; while (TEST--) { int.. 2020. 12. 1.
치킨 쿠폰 문제: 처음에 교환 쿠폰 n장이 있고, k장을 사용하면 1장의 쿠폰을 줄 때, 최대 몇 마리의 치킨을 받을 수 있는가? 사용한 총 쿠폰 수를 t라고 하자. 처음 n장이 있으니 t의 초기값은 n이다. 새로 받을 수 있는 쿠폰은 n // k 장이다. t += n // k * 가지고 있는 쿠폰으로 최대한 많이 교환 이때 남는 쿠폰은 n // k + n % k 장이다. n = n % k + n // k * 교환하지 못한 n % k 장 + 이제 새로 받은 n // k 장 이것을 새로 받을 수 있는 쿠폰이 0장이 될 때까지 반복하면 된다. t = n while n//k > 0: t += n//k n = n//k + n%k 이제 t를 한번에 구하자. k개의 쿠폰을 사용하면 1개의 쿠폰을 받으므로, k - 1개의 쿠폰.. 2020. 11. 25.
Codeforces Round #686 (Div. 3) ABCD import sys input = sys.stdin.readline for TEST in range(int(input())): n = int(input()) for i in range(n-1): print(i+2, end=" ") print(1) A - Special Permutation 한 칸씩 옆으로 밀면 Ai != i가 성립한다. import sys input = sys.stdin.readline for TEST in range(int(input())): n = int(input()) d = {} # appearance, ind s = [*map(int, input().split())] for i, c in enumerate(s): try: d[c] = [d[c][0]+1, d[c][1]] exce.. 2020. 11. 25.
Educational Codeforces Round 98 (Rated for Div. 2) ACD import sys input = sys.stdin.readline for TEST in range(int(input())): n, m = map(int, input().split()) p, q = min(n, m), max(n, m) q -= p print(n+m+max(0, q-1)) A - Robot Program 로봇이 멈추지 않고 최선의 방법으로 가는 방법은 긴 쪽으로 두 칸, 짧은 쪽으로 한 칸 움직이는 것이다. 따라서 위와 같은 방법으로 최대한 멀리 간 다음 두 칸 움직이고 한 칸 쉬는 것이 최선(중 하나)이다. #include using namespace std; typedef pair pii; int main() { ios::sync_with_stdio(0); cin.tie(0); cou.. 2020. 11. 20.
Codeforces Round #684 (Div. 2) ABC1 import sys import collections input = sys.stdin.readline deque = collections.deque for _ in range(int(input())): n, c0, c1, h = map(int, input().split()) s = input().rstrip() zCnt, oCnt = s.count('0'), s.count('1') print(min(c0*zCnt + c1*oCnt, c0*zCnt + c0*oCnt + h*oCnt, c1*oCnt + c1*zCnt + h*zCnt)) A - Buy the String 문자열 중 일부만 바꾸는 것으론 절대 최대 이익을 볼 수 없다. 따라서 0을 모두 1로 바꾸거나, 1을 모두 0으로 바꾸거나, 그대로 구매하.. 2020. 11. 18.

티스토리툴바