[프로그래머스 lv3] 최고의 집합 풀이
해설가장 단순하게 백트래킹 방법이 떠오르지만, 백트래킹으로 n개의 합이 S가 되는 모든 경우를 탐색하면 TLE가 발생한다.dp 점화식도 세울 수 있지만, n과 s의 입력범위가 너무 커 해당 방법도 TLE가 날 것이 분명하다. 이 문제는 완전 탐색 없이 간단한 트릭을 통해 해결할 수 있다.특정 배열의 원소의 곱이 최대가 되려면, 각 원소가 최대한 균등해야 한다.예를 들어 n = 4 이고 s = 10일 때, 각 원소를 최대한 균등하게 하려면 s/n = 10/4 = 2 를 4개 마련하고 {2, 2, 2, 2} 여기에 나머지 2를 하나씩 더해준다. 결과적으로 {2, 2, 3, 3}이 최대 곱을 만드는 배열이 된다. n > s 이면 자연수 n개의합이 s가 되는 경우가 없으므로 {-1}을 리턴한다.n 최종 배열을 ..
2022. 9. 4.
[프로그래머스 lv3] 추석 트래픽 풀이
해설요청 종료 시간과 수행시간이 여러 개 주어질 때, 1초당 최대 처리량을 구하는 문제이다. 1) 문자열을 순회하면서 파싱하고, 요청 시작시간과 요청 종료시간을 구해 각각을 다른 벡터에 넣어준다. 문자열을 파싱할 때는 sscanf 함수를 사용하면 포맷에 따른 정보를 바로 가져올 수 있다. hh, mm, ss, sss, t1(T의 소수점 앞부분), t2(T의 소수점 뒷부분)을 파싱 하고, 종료 시간을 정수형 시간으로 바꾼 뒤 시작 시간을 구해보자. T의 소수점 앞부분 t1에 대하여, 시작시간을 만들려면 종료시간에서 t1*1000-t1을 빼주어야 한다. t1*1000이 아닌 t1*1000-t1인 이유는, 처리시간에 시작과 끝을 포함한다고 주어졌기 때문이다. 예를 들어, 종료 시간이 7000이고 2초 동안 ..
2022. 8. 31.