Henzee's Archive

문제 링크     문제 분석한 개의 회의실이 있고, N개의 회의의 시작 시간과 끝나는 시간이 주어졌을 때 최대로 사용할 수 있는 회의의 최대 개수를 구하는 문제이다.  문제 풀이 문제를 읽고 회의 시간에 대한 표를 그려봤을 때,회의가 최대한 많이 이루어지려면 끝나는 시간이 중요하다는 것을 알았다. 그래서 우선순위 큐를 끝나는 시간을 기준으로 오름차순 정렬한 뒤 회의 시간을 넣고,현재 회의의 끝나는 시간과 다음 회의의 시작 시간을 비교해서 시작 시간이 같거나 크다면 개수를 세고,그렇지 않다면 개수를 세지 않는 방법으로 풀어야겠다고 생각했다.   최종 제출 코드 #include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin..

백준 19598번 - 최소 회의실 개수 (골드 5)     문제 분석N개 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하는 문제이다.N의 범위가 1부터 100,000까지 이므로 최소 회의실 개수는 1 이상 N 이하라는 것을 알 수 있다. 문제 풀이시작 시간을 기준으로 회의 시간을 오름차순 정렬한다.회의가 끝나는 시간을 우선순위 큐(최소힙)에 담아 다음 회의 시작 시간과 비교하며 갱신해준다.  최종 제출 코드#include #include #include #include using namespace std;int N, roomCnt = 1; // 회의실 개수는 1개 이상vector> mTimes;priority_queue, greater> pq; // 최소힙int main(){ ios::sync_wi..

백준 1946번 - 신입 사원 (실버 1)     문제 분석채용에 선발되기 위해서는 다른 모든 지원자보다 서류 순위나 면접 순위가 적어도 하나는 높아야 한다.예를 들어, 지원자들의 서류/면접 순위가 아래와 같다면[3, 2] [1, 4] [4, 1] [2, 3] [5, 5][5, 5] 순위를 가진 지원자는 서류 순위와 면접 순위 모두 다른 지원자들 보다 낮기 때문에 선발될 수 없어서 선발 인원은 4명이 된다.  처음 시도처음 생각해낸 아이디어는 아래와 같다.1) 서류 순위를 오름차순 정렬한다.2) 두 번째 지원자부터 자기 앞에 있는 모든 지원자와 비교하여 면접 순위를 비교한다.3) 해당 지원자의 면접 순위가 앞에 있는 지원자들 보다 면접 순위가 낮다면 선발한다. 아이디어대로 구현했더니, 시간 초과가 났다...

백준 16953번 - A -> B (실버 2)     문제 분석문제를 보자마자 예전에 풀었던 숨바꼭질 문제가 생각나서 바로 BFS 이용해 풀면 되겠다고 생각했다.이동할 수 있는 두 가지 경우의 수(×2, ×10+1)를 큐에 넣고 이 수가 B와 같아지면 해당 깊이를 출력한다. 이때, A의 깊이를 1로 넣기 때문에 출력 시 원래 깊이 + 1이 된다.반복문을 종료했는데도 종료 조건에 들어가지 않았다면, -1을 출력한다.  처음 시도로직 상 틀린 부분이 없는데 틀렸습니다 가 뜨길래 뭐지.. 싶어서 반례를 한참 찾아보다 보니 연산 시 값이 무수히 커지는 것을 생각 못하고 long long 타입이 아닌 int 타입으로 변수를 선언해줘서 오버 플로우가 난 것이었다.더보기#include #include #include..