연속하는 자연수의 곱? (Python)

1. 문제 

- 연속하는 자연수 두 개 이상 곱해서 만들 수 있는 값을 크기 순으로 나열한 수열 arr가 있다.

ex) 2, 6, 12, 20, 24, 30, 42...

- 자연수 n이 매개변수로 주어질 때 arr [n]을 return 해주는 함수 만들기

- n은 1~10^6

 

2. 풀이

- 일단 arr의 요소들을 나열해보며 규칙을 발견해보자

(0) 1*2 = 2

(1) 2*3 = 6

(2) 3*4 = 12

(3) 4*5 = 20

(4) 2*3*4 = 24

(5) 5*6 = 30

(6) 6*7 = 42

(7) 7*8 = 56

(8) 3*4*5 = 60

(9) 8*9 = 72

(10) 9*10 = 90

(11) 10*11 = 110

(12) 4*5*6 or 2*3*4*5 = 120

(13) 11*12 = 132

(14) 12*13 = 156

(15) 13*14 = 182

(16) 14*15  or 5*6*7 = 210

(17) 15*16 = 240

(18) 16*17 = 272

(19) 17*18 = 306

(20) 6*7*8 = 336

(21) 18*19 = 342

(22) 19*20 = 380

(23) 20*21 = 420

(24) 21*22 = 462

(25) 7*8*9 = 504

(25) 22*23 = 506

#arr의 index가 4의 배수일 때마다 연속하는 세 개의 정수가 곱해진 값이 들어가는 줄 알았으나 아닌 것을 확인

 

- 입력 n을 받고 리스트 arr에 다양한 조건들을 비교해가며 하나씩 원소를 넣어준 후, arr의 마지막 요소를  return 하는 방식?

ex) n=7라면? (위에 있는 표는 arr, 아래에 있는 표는 dp)

1)

2

2

2)

2

6

2

6

3)

2

6

12

2

6

20

4)

2

6

12

20

2

6

12

20

5)

2

6

12

20

24

2

(6)

12,24

20

6)

2

6

12

20

24

30

2

12,24

20

30

7)

2

6

12

20

24

30

42

2

12,24

20

30

42

 

dp의 인덱스 i에는 i로 끝나는 값들이 저장되어 있다.

 

위의 그림과 같이 새로운 요소를 arr에 넣을 때는 다음의 조건들을 고려해야 한다.

#n*(n-1) vs (n보다 작은 dp 인덱스를 훑으면 그 요소에 n을 곱한 값) -> 더 작은 값을 arr에 넣어준다.

#dp에 있는 요소를 활용하여 arr를 채운 경우에는 dp를 규칙에 맞게 갱신해 줌