풀이의 핵심은 다이나믹 프로그래밍이다. 0. dp[i]의 값은 'i를 1로 만들기 위한 최소 연산 횟수'를 의미한다. 1. 2부터 n까지 i반복: dp[i]는 dp[i-1]에 1을 더한 값으로 초기화. 만약 i가 2의 배수라면: dp[i]=min(dp[i], dp[i/2]+1)로 초기화한다. 만약 i가 3의 배수라면: dp[i]=min(dp[i], dp[i/3]+1)로 초기화한다. 2. dp[n]을 출력한다. 0. dp를 벡터로 선언하면, OutofBounds에 안걸린다. 1. i가 6의 배수라면 2로도, 3으로도 나눠 떨어진다. 3으로 나누었을 때의 횟수가 더 적으므로 2부터 처리하도록 한다. 정답 소스코드 #include using namespace std; int n; int main() { ios..

재귀와 동적계획법으로 풀 수 있다. 1. 재귀(브루트포스) 재귀함수의 변수로는 날짜(인덱스) - int L, 누적상담료 - int psum 으로 설정하였다. 현재 날짜를 L이라고 하자. 날짜 L에 상담을 할 것인지 하지 않을 것인지 선택을 해야 한다. 1. 날짜 L에 상담하기로 선택했다면, 다음에 선택할 수 있는 날짜는 언제인가? 바로 날짜 L+T[L]부터 상담이 가능할 수 있지 않은가? 그리고 여태껏 누적되어온 상담료 psum에 오늘 선택한 상담료 P[L]을 더한다. void f(int L, int psum) { ... f(L+T[L], psum+P[L]); } 다만 조건이 있다. 상담을 진행하는 도중에 휴가날을 맞이할 수는 없는 노릇이다. 그래서 상담할지 선택하기 전에, 다음 상담이 가능한 날짜(L+..