프로젝트 오일러 11번 문제를 풀어간 방법

0. 프로젝트 오일러라는 사이트는

수학적 문제들을 컴퓨터 프로그래밍으로 하나씩 해결해가는

퀴즈 풀이 사이트이다.

몇 가지 풀어보다가 '이런 풀이법 어떨까' 싶어서 공유한다.





1. 문제 11번.

2. 풀이 과정

일단 20*20의 숫자들을 배열로 만들 필요가 있었다.

수평, 수직, 대각선 방향으로 연속된 네 개의 숫자를 특정할 수 있어야 하기 때문에

일단 리스트형 자료형으로 만들었다.



그리고 배열을 쳐다보고, A4용지에 네모를 그려가던 도중

특이한 규칙성이 보이기 시작했다.

숫자가 4개 연속되어 나타나려면 '여유공간'이 필요하다는 것을 깨달았다.

0번째줄 16번째에 위치한 '50'을 보면

오른쪽으로 최소한 3칸의 여유공간이 있어야만 '50'부터 오른쪽으로 4개의

'연속된 숫자들'이 완성될 수 있다.



지금 정리해보면서 내가 문제를 잘못 풀었다는 사실을 알아냈는데,

문제를 풀고 있을 때까지만 하더라도 다음과 같은 아이디어로 접근했다.

네모가 쳐진 부분에 위치한 숫자들에서 '이동 가능한 방향'은 총 3가지: →, ↘, ↓

각각 '이동'하는 방법은 이렇다.

→: i + 1, 2, 3으로 인덱싱 (1씩 늘어남)
↘: i + 21, 42, 63으로 인덱싱 (21씩 늘어남)
↓: i + 20, 40, 60으로 인덱싱 (20씩 늘어남)

아직 한 가지 방향이 더 남았는데 그건 아래 사진과 같다.

↙: i + 19, 38, 57으로 인덱싱 (19씩 늘어남)

그래서 해당 숫자들의 위치를 어떻게 가져올까 하다가

numpy의 기가막힌 부분 인덱싱 방법을 차용하기로 한다.

numpy의 슬라이싱은 가히 예술적이다. 이렇게 쉽게 배열을 선택할 수 있다.

변수 a에 20*20의 2D matrix를 만들었고,

변수 b에 0부터 16번째까지 담는다.
(슬라이싱은 마지막 번호 미포함으로 인해 0:17로 적음)

변수 c는 ↙방향 숫자배열을 찾을 '시작위치들'을 담았다.
( [3:20, 0:16]이 아니라 [0:16, 3:20]임에 유의해야 한다)

이제 시작 위치부터 하나하나 꺼내오며 곱셈을 해보는 일만 남았다.

b에서는 세 방향으로 진행해서 가장 큰 값을 갱신하도록 만들었고

c에서는 한 방향으로 또 진행해서 가장 큰 값을 갱신하도록 만들었다.



답은 맞았는데, 문제를 잘못 풀었다는 이야기를 위에서 했었다...

그 이유는 다음과 같다...

방향별 인덱싱을 시작해야 할 위치를 누락했다.

빨간색: 오른쪽으로 진행하는 경우엔 아래 세 줄이 추가되어야 하고,

파란색: 아래쪽으로 진행하는 경우엔 오른쪽 세 줄이 추가되어야 했다.

두 가지 모두 겹치는 구간은 노란색의 ↘방향 뿐이다.





3. 정답

70600674