본문 바로가기

전체 글91

치킨 쿠폰 문제: 처음에 교환 쿠폰 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.
Codeforces Round #683 (Div. 2, by Meet IT) AB import sys input = sys.stdin.readline for _ in range(int(input())): n = int(input()) print(n) for i in range(n): print(i+1, end=" ") print() A - Add Candies 한 바구니를 선택한다는 조건을 무시하면, 사탕을 n번 넣었을 때 모든 바구니에 똑같이 (n * (n+1))/2 개의 사탕을 넣게 된다. 이때 각 바구니에 들어있는 사탕 수는 처음과 같이 등차 +1의 관계를 가진다. 따라서 1번 바구니부터 1, 2, 3... 순서로 빼주면 모든 바구니가 같은 수의 사탕을 가지게 된다. 결론은 1번부터 n번까지 순서대로 한 번 씩 선택하면 된다. #include using namespace std;.. 2020. 11. 16.
Queue 개요 한 쪽 끝에선 삽입, 다른 쪽 끝에선 삭제가 일어나는 자료구조 Queue의 성질 First-in First-out (FIFO), 즉 선입선출 방식으로 객체를 담는다. rear에 삽입하고 front에서 삭제한다. Queue 대표적인 operation은 enqueue, dequeue가 있고, 추가로 front, size, empty 등을 지원할 수 있다. Array 또는 Linked List로 구현할 수 있다. Array의 크기를 변경하기 곤란하다는 점을 고려하여 환형으로 구성하면 시간복잡도를 낮출 수 있다. 배열에서 큐의 시작점, 끝점, 크기를 기억하는 변수를 만들어서 구현할 수 있다. 아래는 Array기반 큐의 구현 예시이다. (Linked list 기반 큐는 SLL과 똑같다.) struct Arr.. 2020. 10. 26.