제대로 풀고 있습니다
.
자, 예를 들어봅시다.
n이 5라고 대충 가정하면
a=1, b=5 에서 (1,4), (2,5) 일 때 들어가봐서 d값을 어찌어찌 계산하겠죠?
(1,4) 에서는 (1,3), (2,4) 에 들어가서 어찌어찌 계산하겠네요.
(2,5) 에서는 (2,4), (3,5) 에 들어가서...
여기서 주목할 것은, a=2, b=4일 때에 대한 계산을 한번 더 한다는 것입니다.
(2,4)에서 시작해서 c값이 n+1이 될 때까지 "새로 추가된 d값"의 최소값은 항상 같을 겁니다. 이거를 한번 더 계산할 필요가 없죠.
즉, 이미 한번 계산된 a,b 세트에 대해서는 계산하지 않고, 결과값만 저장해서 가지고있으면 됩니다.
