Level. 2
문제
콜라츠 추측이란 로타르 콜라츠(Lothar Collatz)가 1937년에 제기한 추측으로 모든 자연수 k에 대해 다음 작업을 반복하면 항상 1로 만들 수 있다는 추측입니다.
1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2.결과로 나온 수가 1보다 크다면 1번 작업을 반복합니다.
예를 들어 주어진 수가 5 라면 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒2 ⇒ 1 이되어 총 5번만에 1이 됩니다.
수가 커졌다 작아지기를 반복하는 모습이 비구름에서 빗방울이 오르락내리락하며 우박이 되는 모습과 비슷하다고 하여 우박수 또는 우박수열로 불리기도 합니다. 현재 이 추측이 참인지 거짓인지 증명되지 않았지만 약 1해까지의 수에서 반례가 없음이 밝혀져 있습니다.
은지는 우박수열을 좌표 평면 위에 꺾은선 그래프로 나타내보려고 합니다.
초항이 k인 우박수열이 있다면, x = 0일때 y = k이고 다음 우박수는 x = 1에 표시합니다.
이런 식으로 우박수가 1이 될 때까지 점들을 찍고 인접한 점들끼리 직선으로 연결하면 다음과 같이 꺾은선 그래프를 만들 수 있습니다.
은지는 이렇게 만든 꺾은선 그래프를 정적분 해보고 싶어졌습니다.
x에 대한 어떤 범위 [a, b]가 주어진다면 이 범위에 대한 정적분 결과는 꺾은선 그래프와 x = a, x = b, y = 0 으로 둘러 쌓인 공간의 면적과 같습니다. 은지는 이것을 우박수열 정적분이라고 정의하였고 다양한 구간에 대해서 우박수열 정적분을 해보려고 합니다.
0 이상의 수 b에 대해 [a, -b]에 대한 정적분 결과는 x = a, x = n - b, y = 0 으로 둘러 쌓인 공간의 면적으로 정의하며, 이때 n은 k가 초항인 우박수열이 1이 될때 까지의 횟수를 의미합니다.
예를 들어, 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로 정의합니다.
* 제한사항
- 2 ≤ k ≤ 10,000
- 1 ≤ ranges의 길이 ≤ 10,000
ranges의 원소는 [a, b] 형식이며 0 ≤ a < 200, -200 < b ≤ 0 입니다.
- 주어진 모든 입력에 대해 정적분의 결과는 227 을 넘지 않습니다.
- 본 문제는 정답에 실수형이 포함되는 문제입니다. 입출력 예의 소수 부분 .0이 코드 실행 버튼 클릭 후 나타나는 결괏값, 기댓값 표시와 다를 수 있습니다.
풀이
#include <string>
#include <vector>
using namespace std;
vector<double> solution(int k, vector<vector<int>> ranges) {
// 1. 우박수열 구하기
vector<double> v, answer;
vector<double> areas;
int num = k;
while(1){
v.push_back(num);
if(num == 1) break;
num = num%2==0?num/2:num*3+1;
}
// 2. 좌표별 적분된값을 저장한다.
for(int i=0; i<v.size()-1; i++){
double area = (v[i]+v[i+1])/2.0;
areas.push_back(area);
}
// 3. 구간에 대항 정적분 값을 구한다.
for(int i=0; i<ranges.size(); i++){
double s = ranges[i][0];
double e = (double)areas.size()+ranges[i][1];
double sum = 0;
// 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이 주어질 수 있으며 이때의 정적분 결과는 -1로 정의한다.
if(s>e || s>areas.size()){
answer.push_back(-1);
continue;
}
for(int j=s; j<e; j++){
sum += areas[j];
}
answer.push_back(sum);
}
return answer;
}
해결방법
- 우박수열을 구한다.
- 좌표별 정적분된 값을 저장한다.
- 주어진 구간별 정적분 값을 구한다. 이때, 주어진 구간의 시작점이 끝점보다 클 경우 -1로 정의한다.
https://school.programmers.co.kr/learn/courses/30/lessons/134239#
'Algorithm > Programers - C++' 카테고리의 다른 글
[프로그래머스] 두 원 사이의 정수 쌍 (0) | 2024.05.04 |
---|---|
[프로그래머스] 후보키 (0) | 2024.04.14 |
[프로그래머스] 광물캐기 / Greedy , DFS(백트래킹) (1) | 2024.02.28 |
[프로그래머스] 디펜스 게임 / priority_queue (1) | 2024.02.27 |
[프로그래머스] 점 찍기 (1) | 2024.02.04 |