등반

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 해설 포인트는 다음과 같다. C[i] = 지금까지 만든 길이가 i인 증가 부분 수열 중 최소 마지막 값 => C의 인덱스를 LIS의 길이와 연관시키고, 최소 마지막 값을 기록해 둠으로써 해당 값 보다 현재 비교할 수열의 값이 큰 경우 길이 i+1인 부분 수열을 만들 수 있다. 이때, C에 저장된 수는 오름차순으로 정렬된다. >> 정렬된 상태이므로 이분 탐색이 가능하다. #include #de..

https://www.acmicpc.net/problem/12034 12034번: 김인천씨의 식료품가게 (Large) 입력의 첫 번째 라인(줄)은 테스트 사례의 케이스의 수 T를 나타냅니다. 이후의 라인은 T개의 테스트 케이스가 이어집니다. 각 테스트 케이스는 두 줄로 구성됩니다. 첫 번째 줄에는 INU 식료품가 www.acmicpc.net 문제 해설 2N개의 가격표를 순회하며 정확히 75% 할인된 가격만 뽑아내 출력하는 문제다. 이 경우 map이나 set은 중복을 없애기 때문에 이용할 수 없다. multimap이나 multiset은 가능하다. 본인은 인덱스를 통한 접근이 유용할 것 같아서 vector로 해결했다. #include #define fio cin.tie(0)->sync_with_stdio(0..

https://www.acmicpc.net/problem/11645 11645번: I’ve Been Everywhere, Man The first line of input contains a single positive integer T ≤ 50 indicating the number of test cases. The first line of each test case also contains a single positive integer n indicating the number of work trips Alice has taken so far. The following n www.acmicpc.net 문제 해설 주인공이 다녀온 모든 도시의 개수를 출력하는 문제다.(중복 없이) 이런 문제는 map[st..

https://www.acmicpc.net/problem/11507 11507번: 카드셋트 예제1 : 12 12 11 13은 잃어버린 P카드 : 12개, K : 12개, H : 11개, T : 13라는 뜻이다. 예제2 : 같은 카드(H02)가 존재하므로 GRESKA을 출력하였다. www.acmicpc.net 문제 해설 잃어버린 카드의 목록이 주어질 때, 카드의 모양을 구분하여 갖고 있는 카드의 수를 출력하는 문제다. 구현 문제에 가깝다고 생각한다. #include #define fio cin.tie(0)->sync_with_stdio(0) using namespace std; #include int main(){ fio; string S; cin >> S; set P, K, H, T; bool dupl ..

https://www.acmicpc.net/problem/11346 11346번: Cornell Party - Retry Ezra Cornell and A. D. White learned their lesson from their last party, so this time they decided to use names instead of identifiers. They also realized that they shouldn’t trust their memories so much, so they’ve decided to write down the guest name www.acmicpc.net 문제 해설 코넬에서 파티를 하는데, 두 명이 각각 참가자들의 명부를 기록한다. 동명이인은 없다. 몇 명이 있는..

https://www.acmicpc.net/problem/11235 11235번: Polling Output the name of the candidate with the most votes. If there is a tie, output out all of the names of candidates with the most votes, one per line, in alphabetical order. Do not output any spaces, and do not output blank lines between names. www.acmicpc.net 문제 해설 가장 많이 등장한 인물의 이름을 출력하는 문제다. 해당 인물이 유일하지 않은 경우, 사전 순으로 정렬해 모두 출력한다. 이런 문제는 map[..

https://www.acmicpc.net/problem/11116 11116번: 교통량 첫 번째 줄에 n (1 ≤ n ≤ 100) 까지의 테스트 케이스의 개수를 입력 한다. 각각의 테스트 케이스에는 박스에서 측정 된 시간 기록의 개수 m (m ≤ 200)을 입력한다. 다음 줄에는 왼쪽 박스에서 www.acmicpc.net 문제 해설 왼쪽 줄을 지나간 시간과 오른쪽 줄을 지나간 시간이 주어질 때, 왼쪽에서 오른쪽으로 지나간 교통량을 구하는 문제다. 왼쪽에서 오른쪽으로 지나간 교통량이 될 수 있는 경우는 왼쪽 줄에 t, t+500이, 오른쪽 줄에 t+1000, t+1500이 존재하는 t이다. map을 이용해 각각 log(n) 시간에 탐색해 해결할 수 있다. #include #define fio cin.ti..

https://www.acmicpc.net/problem/10689 10689번: Hamza Hamza Darwish (AKA cpphamza) (an ICPC world finalist who participated in the 2006 ICPC in Texas and the 2008 ICPC in Banff, a previous software engineer at IBM and a current one at imo.im) decided one day with his coach Mohamed Mahmoud Abd El-Wahab (AKA fe www.acmicpc.net 문제 해설 각 테스트 케이스마다 문제 수가 주어지고 문제마다 문제가 속한 카테고리가 주어진다. 주인공은 첫 문제부터 문제를 푸는데,..

https://www.acmicpc.net/problem/10527 10527번: Judging Troubles The NWERC organisers have decided that they want to improve the automatic grading of the submissions for the contest, so they now use two systems: DOMjudge and Kattis. Each submission is judged by both systems and the grading results are compared to make s www.acmicpc.net 문제 해설 DOM과 Kattis에서 각각 채점한 기록이 주어지는데, 각각의 기록의 순서가 뒤죽박죽이 되었다. 이..

https://www.acmicpc.net/problem/9733 9733번: 꿀벌 각각의 일을 한 횟수와 비율을 공백으로 구분하여 출력한다. 출력은 {Re,Pt,Cc,Ea,Tb,Cm,Ex} 순서대로 하며, 비율은 소수점 둘째 자리까지 출력한다. 주어진 목록에 없는 일은 출력하지 않는다. 입력의 www.acmicpc.net 문제 해설 꿀벌이 하는 일들의 총 횟수, 각각의 횟수를 기록하고, 횟수와 전체 대비 비율을 출력하는 문제다. #include #define fio cin.tie(0)->sync_with_stdio(0) using namespace std; #include #include #include #include int main(){ fio; map map_; string S; double to..