본문 바로가기

Algorithm/BOJ47

BOJ 2019 - 순회강연(Greedy) www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net - 짧게 걸리면서 페이가 높은 순으로 강연을 해야 가장 높은 수익을 올릴 수 있다. 현재 소요기간을 카운트하기 위해서 우선순위 큐를 이용해서 시행한 강연만 페이에 대한 최대힙에 남도록 로직을 구현했다. #include #include #include #include using namespace std; int n, ans; vector a; priority_queue pq; .. 2021. 4. 12.
BOJ 16434 - 드래곤 앤 던전(시뮬레이션, binary search) www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net - 예제 입력과 출력값을 통해서 대충 이분탐색인 것은 파악할 수 있었는데, 방타입이 몬스터 방인 경우를 구현하기가 참 햇깔리는 문제였다. - 용사가 먼저 몬스터에게 선공을 한다는 것을 유의해서 구현을 해야된다. #include #include #include #include using namespace std; #define ull unsig.. 2021. 4. 11.
8980 - 택배(greedy) www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net - 운반거리가 짧은 구간. 즉 도착지가 가까운 순으로 배송정보를 정렬하고, 지나가는 마을마다 담을 수 있는 박스의 최대치는 답에 더해나가는 그리디 방식으로 접근했다. #include #include #include using namespace std; // 도착지가 가까운 순으로 배송정보를 정렬하고 // 트럭이 지나가는 마을마다 트럭이 상자를 실을 수 있는 최대치를 모두 더한다 // 경로상에.. 2021. 4. 1.
[boj]15723 - n단논법(Floyd Warshall, string 입출력) www.acmicpc.net/problem/15723 15723번: n단 논법 m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다. www.acmicpc.net - 플로이드 와샬 알고리즘을 알고 있으면 쉽게 풀 수 있는 문제이다. - 플로이드 와샬을 통해서 입력을 통해 주어진 논증 외에도 2~n단 논법을 통해서 징검다리 식으로 증명할 수 있는 논증에 대해서 차례차례 DP 스타일로 증명해 나갈 수 있다. - string 전체를 입력으로 받을 때 getline(cin, string)을 쓰는데 이전에 cin으로 입력을 받았다면 꼭 flushing을 해서 버퍼에 남아있는 '\n'을 제거 해줘야한.. 2021. 4. 1.

티스토리툴바