알고리즘/Backjoon
[C] 1463 - 1로 만들기
ShinDongJun
2020. 1. 9. 19:01
문제 링크 : https://www.acmicpc.net/problem/1463
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define min(a,b) ((a)<(b) ? (a) : (b))
int array[1000001]={'\0'};
int main(void){
int N,i;
scanf("%d",&N);
array[1] = 0;
for(i = 2; i <=N; i++){
array[i] = array[i-1]+1;
if(i%2 == 0){
array[i] = min(array[i], array[i/2]+1);
}
if(i%3 == 0){
array[i] = min(array[i], array[i/3]+1);
}
}
printf("%d",array[N]);
}
|