https://www.acmicpc.net/problem/11444 F[2n-1] = F[n]^2+F[n-1]^2F[2n] = (F[n-1]+F[n+1])*F[n] = (2*F[n-1]+F[n])*F[n] 위의 두 점화식을 이용하여 메모이제이션을 한다. 1234567891011121314151617181920212223242526272829303132333435#include #include using namespace std;typedef long long ll; map d;ll mod=1000000007; ll f(ll n){ if(n0) return d[n]; if(n%2) { ll m=(n+1)/2,a=f(m),b=f(m-1); d[n]=(a*a+b*b)%mod; return d[n]; } els..
https://www.acmicpc.net/problem/9935 문자열과 폭발 문자열이 주어졌을 때 모든 폭발이 끝났을 때의 문자열의 상태를 출력하는 문제이다. 2개의 스택 st, temp을 둔다. 문자열을 쭉 스캔하면서 폭발 문자열의 끝과 서로 같지 않거나 st의 크기가 폭발 문자열의 크기보다 작을 때는 그냥 st에 넣어준다. 그러다가 폭발 문자열의 끝과 같은 시점에서 st에서 하나씩 빼서 temp 옮기면서 폭발 문자열 전체와 같은지 확인한다. 만약 같다면 다 옮긴 후 temp에서 없애주고 중간에 같지 않다면 다시 st로 옮겨준다. 최종으로 st에 남은 문자열이 정답이다. 스택에 역순으로 저장되어 있으므로 temp에 다 옮긴후 하나씩 빼면서 출력해주면 된다. 12345678910111213141516..