판교의 메타몽

The link : leetcode.com/problems/gas-station/ Gas Station - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 풀이는 다음과 같다. 1. 정답으로 출력할 출발 위치인 index, 출발 위치에 따라 변하는 가스의 충전값 indexsum, 전체 가스 충전값을 구할 totalsum 3가지 변수를 세운다. 2. for문을 gas의 size만큼 돌린다. 3. indexsum의 값은 indexsum += gas[i] - co..

링크 : www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 처음에 문제를 주의깊게 읽지않아 해석을 잘못했다. 입력되는 값들은 '점수'가 아니라, '순위'이다. 즉, 숫자가 적을수록 유리한 입지에 있다는 뜻이다. 문제를 잘못해석한 탓에 몇 차례 실수를 겪었다. 문제를 푼 방법은 다음과 같다. (1) 오름차순으로 나열한다. 이렇게해서 서류심사는 정렬이 되었으므로, 이제 면접심사(두 번째 값)만 비교하면 된다. (2) v[0]에 위치한 사람은 ..

링크 : www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 1. 오름차순으로 정렬한다. 2. 0, 0~1, 0~2, ... 0~N번째 합을 누적시킨다. 누적시키는 방법은 2중 for문 구현도 있고, 아래처럼 DP를 사용해도 무방하다. 별 생각 없이 풀 수 있었던 문제였다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(NULL); cin.tie(NULL); int n = 0, arr[1001..

링크 : www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 처음에는 순서대로 값을 받고 직접 두 번째 값을 나열하기 위한 비교 함수를 선언했다. 그런다음 DFS방식으로 문제에 접근했고, 테스트 케이스를 통과하였다. #include #include #include using namespace std; int n = 0, temp = 0, ans = 0; vector v; bool compare(pair& a, pair& b) { if (a.second == b.second) return a.second < b.second; else return a.second < b.second..

링크 : www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제의 핵심은 '그리디 기법'으로, 가장 가능성이 높은 지점을 선택하면 된다. 이 문제는 대상이 '동전'이며, 모든 동전이 5의 배수로 떨어져 오름차순으로 배열되서 제공되기 때문에 어려움 없이 풀 수 있었다. 핵심은 원하는 값 보다 크지 않은 값을 채택하면 된다는 점이다. #include using namespace std; int mai..