https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 테스트케이스를 보면, 중복된 숫자가 들어와서 multimap을 써서 전투력에 해당하는 여러 개의 칭호를 저장해야하나 순간 고민했다. 그런데 문제를 다시 한 번 잘 살펴보면, 어차피 첫 if문에 걸리기 때문에 2번째 중복되는 칭호는 신경 쓸 필요가 없어진다. 그리고 if문에 해당되는 값을 찾기 위해서는 set의 lower_bound 메소드를 써서 간편하게 ..

https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 가능한 한 최대한 이 중요한 문구이다. 1,2 번으로 풀이 방식이 안내되어있지만 간단히 말하면 min(상한액, 예산)은 필수로 배정해야하되, 최대한 많은 예산을 써야한다는 것이다. 상한액을 찾기 위해 binary search를 한다. 이 때 반드시 모든 지방에 최소한 상한액까지는 배정되어야한다는 점을 이용해 포인터 이동 기준은 배정 가능한 지방의 수로 삼는다. #include #include..

https://www.acmicpc.net/problem/20006 20006번: 랭킹전 대기열 모든 생성된 방에 대해서 게임의 시작 유무와 방에 들어있는 플레이어들의 레벨과 아이디를 출력한다. 시작 유무와 플레이어의 정보들은 줄 바꿈으로 구분되며 레벨과 아이디는 한 줄에서 공백 www.acmicpc.net 적당한 자료구조에 주어진 조건에 따라 잘~ 구현하면 된다. 방 정보를 담는 vector를 쓰는데, 한 방에 담는 구성원들은 이름에 따라 정렬될 수 있도록 set을 쓴다. #include #include #include using namespace std; vector ppl; vector rooms; int main() { int p, m; cin >> p >> m; int level; string ..

https://school.programmers.co.kr/learn/courses/30/lessons/118669?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 다익스트라의 업그레이드 + 업그레이드 ver.이다. 1. 비교 기준이 거리가 아니다. 비교기준은 intensity로, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간이다. 이를 자세히 보는 것을 놓쳤다가 시간이 오래걸렸다..ㅠ 2. 산봉우리를 올라가는 경로/ 내려가는 경로를 둘 다 구할 필요는 없다. 3. 출발점과 도착점이 여러 개이다. 출발점과 도착점을 각각 하나씩 골라..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이전에 풀었던 인터넷 설치와 굉장히 유사한 문제이다. 인터넷 설치 문제에서는 남은 것중 제일 가격이 비싼 것의 가격이 공유기 설치 문제에서는 가장 인접한 두 공유기 사이의 거리로, 측정 기준이 된다. 이를 기준 삼아 공유기의 최소 거리를 이분 탐색한다. 여기서 쉬운 문제 풀이를 위해 첫 번째 집을 시작 기점으로 삼는다. 물론 첫 번째 집에 반드시..

투 포인터 활용 문제로 너무 좋은 문제라고 생각한다. 평소에 투 포인터를 풀긴 풀되 패턴화하지 못해서 실수가 잦았기 때문에 이 문제를 통해 패턴화하는 데 도움이 되었다. 연속 부분 수열에 대한 시작과 끝 구간을 지정한다. 주로 시작 구간을 움직일 때는 구간을 줄이는 일이기 때문에, 최대 개수가 늘어날 일도 없고, 갱신을 할 필요가 없다. 따라서 오른쪽 끝구간을 기점으로 값을 갱신하는 일을 수행하면 된다. 대신 이 때 늘어나기 전에 갱신을 해야 한다. 늘어난 후에는 그 때 순간에 최대 개수가 k를 초과하는 일이 발생할 수 있기 때문이다. 이 경우는 추가적인 iteration을 통해 시작점을 움직임으로써 구간을 줄이는 방식으로 처리될 예정이다. 여기서 어차피 숫자는 1 ~ 200,000 까지로 정해져 있으므..