궤도

문제 풀이 myunji.tistory.com/298 [백준] 9095번 : 1, 2, 3 더하기 문제 풀이 dp로 풀면 더 빠르겠지만 난 그냥 백트래킹으로 풀었다. 3~1을 빼서 음수가 되지 않으면 계속 빼주면서 백트래킹 재귀 함수를 호출한다. 소스코드 #include using namespace std; int cnt; void backtr myunji.tistory.com 이 문제를 풀 때는 n이 11보다 작기 때문에 재귀함수로 풀 수 있었다. 하지만 이번엔 n이 1,000,000까지 들어올 수 있기 때문에 재귀함수로 풀면 시간이 너무 오래 걸릴 것이다. 그래서 동적계획법(dp)로 풀어야 한다. 특정 수 i에 대해 i를 1, 2, 3의 합으로 나타내는 방법은 다음과 같다. (i-1을 1, 2, 3의 ..