그랬었습니다

이 문제 역시 Dynamic Programming으로 해결해야 한다. 이 문제는 문제 그대로 큰 숫자를 나누고, 빼면서 접근하면 안 된다. 만약 그렇게 한다면 숫자가 3과 2로 나누어 떨어지는지 검사하는 데에만 엄청난 리소스가 낭비된다. 반대로 생각해보자. 2로 나누어 떨어지는 수는 2로 나눈 몫의 2배와 같은 값이다. 3으로 나누어 떨어지는 수는 3으로 나눈 몫의 3배와 같은 값이다. 그렇다면 역으로 작은 수에 2나 3을 곱하고, 1을 더하면서 숫자를 늘려가면 된다. 1부터 시작한다. 1의 3배는 3이다. 한 번의 연산이니 1을 입력한다. 1의 2배는 2이다. 한 번의 연산이니 1을 입력한다. 1+1은 2이다. 그런데 2에는 이미 숫자가 입력되어 있다. 비교 후 더 작은 값을 넣는다. 이렇게 하면 배열..