Techbrad

1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 접근 방법 1. 최대 가격을 구하는 것이므로 바구니에 들어가면서 가격이 제일 비싼 보석을 찾아야한다. 처음에는 바구니를 N번 돌며 해당하는 보석의 후보군을 모두 찾고 후보군에서 전체를 탐색하며 가장 가격이 비싼 보속을 찾아야한다고 생각했지만 우선순위 큐를 사용해서 시간을 줄일 수 있다. 2. 담을 수 있는 무게가 작은 바구니부터 순회를 시작해야한다. 그래야 모든 보석을 순차적으로 빠짐없이 후보에 ..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A B라고 한다면 역방향으로 풀면 쉽게 풀 수 있다. 기본적으로 2를 계속 나누고 끝자리가 1이면 1을 제거해 준다. 하지만 종료 조건을 잘 생각해봐야한다. 첫 제출코드 A, B = map(int, input().split(" ")) cnt = 1 while True: if A == B: break elif B < A: cnt = -1 break elif B % 10 == 1: B = B // 10 cnt += 1 else: B = B//2 cnt += 1 print(cnt) 이렇게 했지만 계속..

1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 접근 방법 처음에는 우선순위 큐를 가지고 풀려고 했으나 실패. 많은 시간을 소비한것에 비해 정답지는 너무 허무했다. 시작 시간을 오름차순으로 정렬 후 종료 시간으로 오름 차순을 정렬한다. 그러면 시작시간이 같은 경우 종료 시간이 빠른 순으로 정렬 된다. 제출 코드 import heapq N = int(input()) meeting_list = [] for i in range(N): s, e = map(int, input().split()) meeting_list.append((s, e)) # 시작 시간이 같은 모임들 중에서 종료시간이 빠른 모임으로 정렬됨. meeting_..

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 이번 문제는 https://techbrad.tistory.com/68 이 문제 유형과 동일하게 보여서 유형을 익숙하게 하고자 풀어보았다. 하지만..... 자꾸 시간초과가 발생했다. 컵라면이고 뭐고 너무 짜증이 났지만 또 다른 블로그를 참고하고 분석했다. 문제 접근 방법 이전에 풀었던 문제와 같이 점수가 높은 순서대로 maxheap을 구성하여 풀었다. 여러번 확인했으나 반목문이 두개여서 O(N2) 시간 복잡..