-
[프로그래머스] 우박수열 정적분 c++Coding Test/programmers 2023. 1. 7. 00:40728x90
문제 설명
예를 들어, 5를 초항으로 하는 우박수열은 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 입니다. 이를 좌표 평면으로 옮기면 (0, 5), (1, 16), (2, 8), (3, 4), (4, 2), (5, 1) 에 점이 찍히고 점들을 연결하면 꺾은선 그래프가 나옵니다. 이를 [0,0] 구간에 대해 정적분 한다면 전체 구간에 대한 정적분이며, [1,-2] 구간에 대해 정적분 한다면 1 ≤ x ≤ 3인 구간에 대한 정적분입니다.
우박수의 초항 k와, 정적분을 구하는 구간들의 목록 ranges가 주어졌을 때 정적분의 결과 목록을 return 하도록 solution을 완성해주세요. 단, 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이 주어질 수 있으며 이때의 정적분 결과는 -1로 정의합니다.
https://school.programmers.co.kr/learn/courses/30/lessons/134239?language=cpp
제한 사항
- 2 ≤ k ≤ 10,000
- 1 ≤ ranges의 길이 ≤ 10,000
- ranges의 원소는 [a, b] 형식이며 0 ≤ a < 200, -200 < b ≤ 0 입니다.
- 주어진 모든 입력에 대해 정적분의 결과는 227 을 넘지 않습니다.
- 본 문제는 정답에 실수형이 포함되는 문제입니다. 입출력 예의 소수 부분 .0이 코드 실행 버튼 클릭 후 나타나는 결괏값, 기댓값 표시와 다를 수 있습니다.
입출력 예
k ranges result 5 [[0,0],[0,-1],[2,-3],[3,-3]] [33.0,31.5,0.0,-1.0] 풀이
정적분(넓이)를 구하기 위해서 각 범위의 사다리꼴 넓이를 구해야 합니다.
- 사다리꼴 넓이 : ( (윗변 + 아랫변) * 높이 ) / 2
위 그래프에서는 y값을 윗변, 아랫변 값으로 지정하고, 높이는 x값이 됩니다.
x값은 1씩 증가하는 인덱스 값입니다.
첫번째 사다리꼴 넓이 = ((y0 + y1) * 1) / 2 입니다. 높이는 항상 1이므로 생략합니다.
5의 정적분 개수 cnt = 6입니다. (5, 16, 8, 3, 2, 1)
정적분 범위는 range[x, y] = [ 0 + x , cnt - y] 임을 알 수 있습니다.
ex) k = 5, range[1, -2] = [0+1, 6-2] = (1 <= x <=3) 구간입니다.
저는 정적분을 구하면서 사다리꼴의 넓이를 구하고, 넓이를 누적한 값을 사용하여 문제를 풀었습니다.
range[1, 0] → s = 1, e = 6 일 때, 정적분은 vec[e] - vec[s] 입니다. vec[e]에는 0~e범위까지 사다리꼴의 넓이가 저장되어 있고, vec[s]는 0~s 범위 까지의 사다리꼴 넓이가 저장되어 있습니다.
그렇기 때문에 vec[e] - vec[s] 를 계산하면 1 <= x <= 6의 정적분 값을 구할 수 있습니다.
이런 원리를 이용한 문제 풀이입니다.
range x값은 0부터 나올 수 있으므로, 사다리꼴 넓이 누적 값의 처음 값은 0을 먼저 삽입합니다.
#include <string> #include <vector> using namespace std; vector<double> solution(int k, vector<vector<int>> ranges) { double prev = k, curr = k, val = 0; vector<double> sumVec; sumVec.push_back(0); while( curr > 1){ if( (int)curr % 2 == 1){ curr = curr * 3 + 1; } else{ curr /= 2; } val += (prev + curr) / 2; sumVec.push_back(val); prev = curr; } vector<double> answer; for(int i = 0; i < ranges.size(); i++){ int s = ranges[i][0]; int e = sumVec.size() -1 + ranges[i][1]; double sum = 0; if(s == e){ sum = 0; } else if(s > e){ sum = -1; } else{ sum = sumVec[e] - sumVec[s]; } answer.push_back(sum); } return answer; }
728x90'Coding Test > programmers' 카테고리의 다른 글
[프로그래머스] 진료과별 총 예약 횟수 출력하기 MYSQL (0) 2023.01.07 [프로그래머스] 성분으로 구분한 아이스크림 총 주문량 MYSQL (0) 2023.01.07 [프로그래머스] 점 찍기 c++ (0) 2023.01.06 [프로그래머스] 디펜스 게임 c++ (0) 2023.01.06 [프로그래머스] 보호소에서 중성화한 동물 MYSQL (0) 2023.01.06