일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 알고리즘
- 맛집
- hackerrank
- 삼성 기출
- BFS
- 에라토스테네스의 체
- 백준
- Algorithm
- 소수
- PS
- 완전탐색
- 시뮬레이션
- 동적 계획법
- SWEA
- dfs
- 구현
- BOJ
- 해커랭크
- DP
- 스택
- 잠실
- sw expert academy
- 백트래킹
- 삼성 SDS 대학생 알고리즘 특강
- 다이나믹 프로그래밍
- koitp
- dynamic programming
- 그리디
- 브루트포스
- C++
- Today
- Total
펭로그
[C++] 삼성 SDS KOITP 전화상담 본문
문제링크 : https://koitp.org/problem/SDS_TEST_CONSULTING
[삼성 SDS 대학생 알고리즘 특강 사전 테스트 A Type 4번 문제]
최대 상담 고객의 수 : 최소 상담시간 조건을 충족해야 한다. 수진이의 근무시간을 최소 상담시간으로 나눈 몫을 취하면 된다.
최소 상담 고객의 수 : 고객들이 원하는 상담시간 모두를 더하면 된다. 단, 수진이의 근무시간을 초과하기 전까지로 한다.
최소 ~ 최대 사이의 값으로 loop를 돌려서 값을 구하면 된다.
1. 고객 당 10점씩 받을 수 있기 때문에 고객의 수 만큼 10점씩 누적시킨다.
2. 모든 고객이 최소 시간만큼만 상담한다고 가정하고 수진이의 근무시간에서 최소 시간만큼만 뺀다.
3. 남아있는 시간을 효율적으로 사용하려면 불만족 지수를 3 -> 2 -> 1 순서로 차감 시켜주면 된다.
4. 모든 고객의 불만족 지수를 1, 2, 3 점수 별로 나누어 각 항목당 부족한 상담 시간을 합산을 한다.
5. 4의 값은 고객이 하나씩 추가될 때마다 반복해서 계산되는 부분이다. 따라서 첫번째 연산시에는 0 ~ minNum 까지 루프를 돌리지만 그 다음 루프인 0 ~ minNum + 1 부터는 0 ~ minNum 까지의 값이 어짜피 중복되므로 minNum ~ minNum + 1 구간만 새로 추가해주면 되기 때문에 이전 루프에서 계산했던 값들을 그대로 활용한다. 이렇게 하기 위하여 루프 바깥에 time1, time2, time3를 선언하였고 idx 변수를 for문에서 초기값을 그대로 사용하는 것을 확인할 수 있다.
6. 최소 상담시간을 제외한 나머지 모든 시간을 일단 전부 빼준다. (2~4에서 구한 값들을 활용하여)
7. 남아있는 시간 만큼 다시 3 -> 2 -> 1 순서로 더해준다.
8. 누적된 값이 이전 루프에서 받았던 점수보다 큰지 작은지 비교하여 계산한다.
매 루프시마다 for문을 N회 실행하지 않고 최초 loop에서만 for문을 N회 실행 후 이후 loop에선 1회만 실행하여 시간을 줄였다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | // KOITP_SDS_Atype_04 #include <bits/stdc++.h> using namespace std; int main() { // freopen("../input.txt", "r", stdin); int T; cin >> T; for (int t = 0; t < T; t++) { int num; int minTime; int workTime; int score = 0; int temp = 0; int remain; cin >> num >> minTime >> workTime; vector<vector<int>> data(num, vector<int>(2)); for(int i = 0; i < num; i++) cin >> data[i][0] >> data[i][1]; int maxNum = min(workTime / minTime, num); int minNum = 0; int tmptmp = 0; for(int i = 0; i < maxNum; i++) { tmptmp += data[i][0]; if(tmptmp < workTime) minNum++; else break; } int time1 = 0, time2 = 0, time3 = 0; int idx = 0; for(num = minNum; num <= maxNum; num++){ temp = 10*num; remain = workTime - minTime * num; for(idx; idx < num; idx++){ if(data[idx][1] == 1) time1 += data[idx][0] - minTime; else if(data[idx][1] == 2) time2 += data[idx][0] - minTime; else time3 += data[idx][0] - minTime; } temp -= time1 + time2 * 2 + time3 * 3; if(remain > time3){ temp += time3 * 3; remain -= time3; } else{ temp += remain * 3; score = max(temp, score); continue; } if(remain > time2){ temp += time2 * 2; remain -= time2; } else{ temp += remain * 2; score = max(temp, score); continue; } if(remain > time1){ temp += time1; remain -= time1; if(remain >= minTime) continue; } else{ temp += remain * 1; } score = max(temp, score); } cout << "#" << t+1 << " " << score << "\n"; } return 0; } | cs |
'Study > PS(Algorithm)' 카테고리의 다른 글
[C++] 삼성 SDS KOITP 보물찾기 (0) | 2018.07.21 |
---|---|
[C++] 백준 BOJ 10799 쇠막대기 (0) | 2018.07.20 |
[C++] 삼성 SDS KOITP 고장난시계 (0) | 2018.07.19 |
[C++] 삼성 SDS KOITP 마지막생존자 (0) | 2018.07.19 |
[C++] 삼성 SDS KOITP 순환공간 (0) | 2018.07.19 |