https://www.acmicpc.net/problem/16165 16165번: 걸그룹 마스터 준석이 정우는 소문난 걸그룹 덕후이다. 정우의 친구 준석이도 걸그룹을 좋아하지만 이름을 잘 외우지 못한다는 문제가 있었다. 정우는 친구를 위해 걸그룹 개인과 팀의 이름을 검색하여 외우게 하는 www.acmicpc.net std::map 을 활용해서 해결한 문제. 입력 범위가 작아서 매번 비교대조하면서 해결해도 괜찮겠다만, 편리하고 깔끔하게 풀기 위해서는 std::map을 사용하면 좋다. std::map 으로 문자열과 숫자 인덱스를 서로 매칭시켜 줄 수도 있고, teamName[Name[i]] = i; 어떠한 팀 $M_i$ 에 어떠한 사람이 포함되어있는지도 맵을 사용하면 깔끔하게 판별할 수 있다. if(memb..

https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 이분 탐색 문제. N이 터무니 없이 큰 숫자라서 시뮬레이션 문제로 보면 시간초과를 피할 수 없다. 이분탐색을 통해서 "사람 N명이 탑승하는데 필요한 최소의 시간" 을 구한다. 이 시간을 T라고 하면, 정확히 T 시간에 사람이 N명 탑승하게 될 것이므로, T-1 시간에는 탑승을 하지 못한 사람들이 생기게 된다. 이 사람들 중에서 마지막 아이가 나오게 되므로, T..

https://www.acmicpc.net/problem/2824 2824번: 최대공약수 첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M(1 ≤ M ≤ 1000)이 www.acmicpc.net GCD 응용 문제. 입력으로 들어오는 수들을 다 곱해내면 범위제한을 훌쩍 초과하게 된다. 오버플로우가 발생하는것을 막기 위해서, 입력으로 들어오는 수들에서 바로 최대공약수를 계산해야 한다. A와 B 두 배열에 입력을 받았을 때, 두 배열에서 임의의 한쌍의 수를 뽑는데 O(N^2) 만큼이 걸리며, 이렇게 뽑아온 두 수의 최대공약수를 정답에 곱해주는 방법으로 ..

https://www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 자료구조 문제. 차량 번호로 주어지는 문자열을 숫자에 매칭시켜줘야 한다. 처음 N줄에 들어오는 문자열들을 1부터 차례대로 숫자에 매칭시켜주고, 다음 N줄에 들어오는 문자열들을 앞서 매칭시켰던것을 이용해서 하나의 숫자 배열로 바꿔준다. 숫자 배열을 비교하면서 탐색하는데, 자기 자신의 뒤에서 자기 자신보다 적은 번호를 매칭받은 번호판이 있다면 자기 자신이 반드시 그 번호판의 차량을 추..

https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net DP 문제 ( 수열의 유도 및 구현 ) 개념을 알고 모르고의 유무로 난이도가 극명하게 갈린다고 할 수 있는 문제. 이 문제에서 요구하는 수열은 "교란순열" 혹은 "완전순열" 이다. 44라는 숫자가 나오면 한번쯤 의심해볼만할듯. dp[i] = (dp[i-1]+dp[i-2])*(i-1) 교란순열을 구하는 DP 점화식은 다음과 같다. DP[i] : i명끼리 조건에 맞게 선물을 분배하는 경우의 수 유도 각각의 사람의 번호를 $a_i$ , 선물의 번호를 $b_i$ 로 둔다. 어떠한 사람 A가 선물을 하는 경우는 $(N-1..

https://www.acmicpc.net/problem/21758 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 부분합 + 그리디 문제. 꿀벌 둘을 A,B ( B가 더 오른쪽에 있는 꿀벌 ) 벌통을 C로 두면 크게 세가지 경우의 수가 있을 수 있다. 1. A < B < C 순 배치. 이 경우에 있어서, 꿀통인 C는 오른쪽 끝에 위치하는것이 가장 이득이 되고, 첫번째 꿀벌 A는 가장 왼쪽 끝에 위치하는것이 가장 이득이 된다. 남은 꿀벌 B가 어디에 있느냐에 따라서, (전체 꿀 + B~C 이동에서의 꿀 - A, B지점에서의 꿀) 을 계산해주면 된다. 벌이 있는 곳에서는 꿀을 딸 수 없기 때문에 A, B 지점의 꿀은 계산에서 따로 빼줘야 함에 유의할것...