티스토리 뷰
https://www.acmicpc.net/problem/1463
n번째 숫자의 값 은 n-1번째, n/2번재, n/3번째 숫자에서 연산을 한 번 추가하여 구할 수 있다. 세 연산 중 가장 작은 값을 선택.
n번째 숫자의 값 <- min( n-1번째 숫자의 값 +1, n/2번째 숫자의 값 +1, n/3번째 숫자의 값+1)
(단 n/2, n/3이 존재하지 않는 경우 infinite)
Pseudo code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | arr[1,000,001] arr[1] <- 0 arr[2] <- 1 arr[3] <- 1 for i <- 4 ... 10^6 do if i % 2 == 0 then temp1 <- arr[i/2] +1 else temp1 <- inf if i % 3 == 0 then temp2 <- arr[i/3] +1 else temp2 <- inf min(temp1, temp2, arr[i-1]+1) print arr[n] | cs |
C++ code
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 31 32 33 34 | #include <iostream> using namespace std; int my_min(int n1, int n2, int n3){ int min1; if(n1 > n2) min1 = n2; else min1 = n1; if(min1 > n3) min1 = n3; return min1; } int main(){ int n; cin >> n; int *arr = new int[n+1]; arr[1] = 0; arr[2] = 1; arr[3] = 1; int temp1, temp2; for(int i = 4; i <= n ; i++){ if(i % 2 == 0) temp1 = arr[i/2]+1; else temp1 = 987654321; if(i % 3 == 0) temp2 = arr[i/3]+1; else temp2 = 987654321; arr[i] = my_min(temp1, temp2, arr[i-1]+1); } cout << arr[n]; return 0; } | cs |