<문제>
- 정수X에 사용할 수 있는 연산은 다음과 같이 세 가지
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
- 어떤 정수 N에 위와 같은 연산을 선택해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최소값을 구하는 문제
[Top-Down 방식]
int go (int n){
if(n==1) return 0;
if(d[n] > 0) return d[n];
d[n] = go(n-1) + 1;
if(n%2 == 0){
int temp = go(n/2) + 1;
if(d[n] > temp) d[n] = temp;
}
if(n%3 == 0){
int temp = go(n/3) + 1;
if(d[n] > temp) d[n] = temp;
}
return d[n]
}
[Bottom-Up방식]
d[1] = 0;
for(int i=2; i<=n; i++){
d[i] = d[i-1] + 1;
if(i%2 == 0 && d[i] > d[i/2] + 1){
d[i] = d[i/2] + 1;
}
if(i%3 == 0 && d[i] > d[i/3] + 1){
d[i] = d[i/3] + 1;
}
}
'알고리즘 > 알고리즘 문제' 카테고리의 다른 글
[python] 프로그래머스 > 스택/큐 > 주식가격 (0) | 2020.08.19 |
---|---|
[python] 프로그래머스 > 멀쩡한 사각형 (0) | 2020.08.16 |
[python] 프로그래머스 > level1 > 자연수 뒤집어 배열로 만들기 (0) | 2020.07.31 |
[python] 프로그래머스 > level1 > 약수의 합 (0) | 2020.07.31 |
[python] 프로그래머스 > level1 > 두 정수 사이의 합 (0) | 2020.07.29 |