인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.
문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅
입력예제 1
10
출력예제 1
12
풀이
-3 point 알고리즘
-소인수 분해해서 2, 3, 5로만 이루어진 수를 찾는다
- 3개의 포인터를 놓고 위치 값에 2, 3, 5로 곱하는데 이때 가장 작은 값으로 다음 값을 바꿔준다
- for문은 2번부터 n번까지, n번째 값이 정답이 된다
- 2, 3, 5로만 곱해진 수에 2, 3, 5를 곱하기 때문에 당연히 2, 3, 5 만으로 이루어진 수가 된다.
- 주의해야 할 점이 있는데 가장 작은 값이 p2, p3, p5에서 중복해서 나올 수 있다.
=> 따라서 min값을 구하고 p2, p3, p5값 중 어떤 값이 min값에 해당하는 지 찾을 때 if문을 사용해 중복으로 ++ 가능하게 한다.
[EX]
1
p2(1) X 2
p3(1) X 3
p5(1) X 5
(2,3,5) => 다음값 2, 포인터2++
2
p2(2) X 2 => 4
p3(1) X 3 => 3
p5(1) X 5 => 5
(4,3,5) => 다음값 3, 포인터3++
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int a[1501];
// 52. Ugly Numbers(3 point)
int main() {
int n, i, p2, p3, p5, min=2147000000;
scanf("%d",&n); //몇 번째 ugly number인지
a[1]=1; //첫 번째 수는 1
p2=p3=p5=1;
for(i=2;i<=n;i++){
if(a[p2]*2<a[p3]*3) min=a[p2]*2;
else min=a[p3]*3;
if(a[p5]*5<min) min=a[p5]*5; //둘 중에 min과 비교해서 작으면 min
if(a[p2]*2==min) p2++; //p2가 min이면 ++
if(a[p3]*3==min) p3++; //else if 아닌 이유는 동시에 min과 같은 값이면 둘 다 위치 이동
if(a[p5]*5==min) p5++;
a[i]=min;
}
printf("%d\n", a[n]);
return 0;
}
'알고리즘' 카테고리의 다른 글
54. 올바른 괄호[stack 활용] (0) | 2021.01.04 |
---|---|
53. K진수 (0) | 2020.12.31 |
50. 영지(DP) (0) | 2020.12.29 |
49. 블록의 최댓값 (0) | 2020.12.28 |
48. 각 행의 평균과 가장 가까운 값 (0) | 2020.12.24 |