henry's PS diary

https://www.acmicpc.net/problem/1463 1로 만드는 최소 연산 횟수는 1에서 N까지 만드는 최소 연산 횟수와 같다. 이를 d[i]이라 하면 이전에 올 수 있는 연산들 중 최소에 1을 더하면 된다. d[i]=min(d(i-1],d[i/3],d[i/2])+1 Top-Down 구현 123456789101112131415161718192021#include #include using namespace std; int n,d[1000001]; int go(int n){ if(n==1 || d[n]) return d[n]; d[n]=go(n-1)+1; if(n%3==0) d[n]=min(d[n],go(n/3)+1); if(n%2==0) d[n]=min(d[n],go(n/2)+1); ret..

https://www.acmicpc.net/problem/1003 f(n)을 호출할 때 f(0)과 f(1)이 각각 호출되는 횟수의 점화식은 d[n]=d[n-1]+d[n-2] 로 같다. 기저값만 1,0과 0,1으로 각각 다르므로 f(1)에 관한 d 배열값이 하나씩 밀려서 나타난다. 따라서 f(0)에 관한 값만 구하고 출력할때 d[n],d[n+1]을 출력해주면 된다. 1234567891011121314151617#include int t,n,d[42]; int main(){ d[0]=1; for(int i=2;i

https://www.acmicpc.net/problem/1526 4와 7을 계속 붙이면서 N보다 작거나 같은 가장 큰 금민수를 찾는다. 12345678910111213141516171819#include int n,ans; void go(int x){ if(x>n) return; ans=ans