프로그래머스
프로그래머스 우박수열 정적분
콩순이냉장고
2022. 12. 19. 18:32
문제URL : https://school.programmers.co.kr/learn/courses/30/lessons/134239
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 접근법 : 문제에 나와있는 콜라츠 추측을 그대로 이용만하면
되는 문제입니다.
1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2.결과로 나온 수가 1보다 크다면 1번 작업을 반복합니다.이조건대로 어떤수든 반드시 1이 나오니 반드시 k라는 숫자를 이용해서
이추측대로 알고리즘을 짜면됩니다. 그리고 매초마다 어떤수가 되는지
작성해서 그수를 기록해봅니다. 그 기록한수를 자세히 확인하면 면적이
어떻게 만들어지는지 확인하면되는데
이와같은 이미지처럼 면적이 쉽게 유추됩니다. 매초마다 작은사각형과 삼각형이 합쳐진 모양으로 면적이 구성이되고
그 면적을 다합하면 해당 면적을 쉽게구할수있습니다. 그렇지만 매초마다 수가 작아지거나 커질수도있기때문에
이전수보다 작아졌다면 현재수를 선택해서 사각형을 만들고 이전수보다 커졌다면 이전수를 선택해서 사각형을 계산해야합니다.
그렇다면 반대로 삼각형은 이전수보다 작아졌다면 이전수를 선택해서 삼각형을 만들고 이전수보다 커졌다면 현재수를 선택해서 삼각형을 만들어야한다는것
그리고 어떤 정수형의 범위만큼의 면적을 구하는거니 그면적들의 누적합을 구해서 구하면 O(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
|
#include<bits/stdc++.h>
using namespace std;
vector<double> solution(int k, vector<vector<int>> ranges) {
vector<double> sum(1, 0);
vector<pair<int, int>> v;
int idx = 0;
int before = k;
while (k > 1) {
v.push_back({ idx++,k });
if (k % 2 == 0)
k /= 2;
else k = k * 3 + 1;
int h = min(before, k);
int h2 = abs(before - k);
sum.push_back(h + (double)h2 / 2.0);
before = k;
}
v.push_back({ idx,k });
for (int i = 1; i < sum.size(); i++)sum[i] += sum[i - 1];
vector<double> res;
for (vector<int>& r : ranges) {
int a = r[0];
int b = idx + r[1];
if (b < a)res.push_back(-1);
else {
res.push_back(sum[b] - sum[a]);
}
}
return res;
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.