Project Euler Problem8

2015. 2. 28. 02:09프로그래밍/알고리즘

728x90
728x90

Largest product in a series

Problem 8

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?



나의 풀이)

연속된 13자리 숫자의 자리별 곱을 구하는 문제이다.

처음에 문자열로 넣어서 잘라서 캐스팅해서.. 스스로 고통을 창조하고 있었는데

아카데미 동기 동생이 "그거 그냥 형 인트로 다 때려박으면 안되나요? po콤마!wer"

노가다로 콤마를 넣으려니 동갑내기 동기가 "그거 정규식 쓰면 편해!"라고 해서..

처음으로 정규식의 맛을 보았다. 잊지 않겠다. 그 더러운 정규식의 맛!



이런식으로 바꿀 수 있었다니! 쓰면 좋다고 하니 나중에 공부 좀 해봐야겠다. 아주 편리.


1차 시도.

각설하고.. 배열로 할까? 포인터로 할까? 고민하다가 결국 배열로 시도.

설계를 대충해서 그런지 머리에서 엄청나게 꼬여서 자꾸 삽질만 반복했다..

for문 2개로 자꾸 하려니 안되는거였는데.. 총 3중까지 들어가야 하는 것!


2차 시도.

지하철에서 수도코드 작성! 역시 생각을 좀 더 했어야 했어..

배열 첨자만큼 문자 2개랑 13개를 반복할 문자가 필요했다.

그리고 한 줄이 총 50개의 숫자니깐 37개까지만 검사하고 다음 줄로 넘어가는 스토리!

(하지만 이게 나중에 엄청난 화근이 되는데..................)



아름다운 글자들!

완벽하다 생각하고 집에 오자마자 앉은자리에서 코딩을 했지만....

결과는 참패. 아무리 답을 쓰고 디버깅을 해도 틀린 답이.........


3차 시도.

디버깅을 열심히 했을 때, 연산에는 아무 문제가 없었다.

그렇다면 가능성.. 혹시?

- 개행이 된 숫자도 인접한 숫자로 여기는가? (이것만은 아니길 바랬는데..)

- 세로나 대각선도 인접으로 여기는가? (이거였으면.. 아마 오늘 밤 샜겠지..)


답은 첫 번째였다. 개행되어 앞으로 간 숫자도 인접한 숫자로..

급히 기존 방식에서 37번까지 실행하지 않고 50번까지 실행하니 바로 답이 나왔다......

역시 코딩은 고통의 연속..


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#define TCOUNT 13
 
...
 
    int sample[20][50={
        {7,3,1,6,7,1,7,6,5,3,1,3,3,0,6,2,4,9,1,9,2,2,5,1,1,9,6,7,4,4,2,6,5,7,4,7,4,2,3,5,5,3,4,9,1,9,4,9,3,4}
        ,{9,6,9,8,3,5,2,0,3,1,2,7,7,4,5,0,6,3,2,6,2,3,9,5,7,8,3,1,8,0,1,6,9,8,4,8,0,1,8,6,9,4,7,8,8,5,1,8,4,3}
        ,{8,5,8,6,1,5,6,0,7,8,9,1,1,2,9,4,9,4,9,5,4,5,9,5,0,1,7,3,7,9,5,8,3,3,1,9,5,2,8,5,3,2,0,8,8,0,5,5,1,1}
        ,{1,2,5,4,0,6,9,8,7,4,7,1,5,8,5,2,3,8,6,3,0,5,0,7,1,5,6,9,3,2,9,0,9,6,3,2,9,5,2,2,7,4,4,3,0,4,3,5,5,7}
        ,{6,6,8,9,6,6,4,8,9,5,0,4,4,5,2,4,4,5,2,3,1,6,1,7,3,1,8,5,6,4,0,3,0,9,8,7,1,1,1,2,1,7,2,2,3,8,3,1,1,3}
        ,{6,2,2,2,9,8,9,3,4,2,3,3,8,0,3,0,8,1,3,5,3,3,6,2,7,6,6,1,4,2,8,2,8,0,6,4,4,4,4,8,6,6,4,5,2,3,8,7,4,9}
        ,{3,0,3,5,8,9,0,7,2,9,6,2,9,0,4,9,1,5,6,0,4,4,0,7,7,2,3,9,0,7,1,3,8,1,0,5,1,5,8,5,9,3,0,7,9,6,0,8,6,6}
        ,{7,0,1,7,2,4,2,7,1,2,1,8,8,3,9,9,8,7,9,7,9,0,8,7,9,2,2,7,4,9,2,1,9,0,1,6,9,9,7,2,0,8,8,8,0,9,3,7,7,6}
        ,{6,5,7,2,7,3,3,3,0,0,1,0,5,3,3,6,7,8,8,1,2,2,0,2,3,5,4,2,1,8,0,9,7,5,1,2,5,4,5,4,0,5,9,4,7,5,2,2,4,3}
        ,{5,2,5,8,4,9,0,7,7,1,1,6,7,0,5,5,6,0,1,3,6,0,4,8,3,9,5,8,6,4,4,6,7,0,6,3,2,4,4,1,5,7,2,2,1,5,5,3,9,7}
        ,{5,3,6,9,7,8,1,7,9,7,7,8,4,6,1,7,4,0,6,4,9,5,5,1,4,9,2,9,0,8,6,2,5,6,9,3,2,1,9,7,8,4,6,8,6,2,2,4,8,2}
        ,{8,3,9,7,2,2,4,1,3,7,5,6,5,7,0,5,6,0,5,7,4,9,0,2,6,1,4,0,7,9,7,2,9,6,8,6,5,2,4,1,4,5,3,5,1,0,0,4,7,4}
        ,{8,2,1,6,6,3,7,0,4,8,4,4,0,3,1,9,9,8,9,0,0,0,8,8,9,5,2,4,3,4,5,0,6,5,8,5,4,1,2,2,7,5,8,8,6,6,6,8,8,1}
        ,{1,6,4,2,7,1,7,1,4,7,9,9,2,4,4,4,2,9,2,8,2,3,0,8,6,3,4,6,5,6,7,4,8,1,3,9,1,9,1,2,3,1,6,2,8,2,4,5,8,6}
        ,{1,7,8,6,6,4,5,8,3,5,9,1,2,4,5,6,6,5,2,9,4,7,6,5,4,5,6,8,2,8,4,8,9,1,2,8,8,3,1,4,2,6,0,7,6,9,0,0,4,2}
        ,{2,4,2,1,9,0,2,2,6,7,1,0,5,5,6,2,6,3,2,1,1,1,1,1,0,9,3,7,0,5,4,4,2,1,7,5,0,6,9,4,1,6,5,8,9,6,0,4,0,8}
        ,{0,7,1,9,8,4,0,3,8,5,0,9,6,2,4,5,5,4,4,4,3,6,2,9,8,1,2,3,0,9,8,7,8,7,9,9,2,7,2,4,4,2,8,4,9,0,9,1,8,8}
        ,{8,4,5,8,0,1,5,6,1,6,6,0,9,7,9,1,9,1,3,3,8,7,5,4,9,9,2,0,0,5,2,4,0,6,3,6,8,9,9,1,2,5,6,0,7,1,7,6,0,6}
        ,{0,5,8,8,6,1,1,6,4,6,7,1,0,9,4,0,5,0,7,7,5,4,1,0,0,2,2,5,6,9,8,3,1,5,5,2,0,0,0,5,5,9,3,5,7,2,9,7,2,5}
        ,{7,1,6,3,6,2,6,9,5,6,1,8,8,2,6,7,0,4,2,8,2,5,2,4,8,3,6,0,0,8,2,3,2,5,7,5,3,0,4,2,0,7,5,2,9,6,3,4,5,0}};
    
    
...
 
    for(i = 0; i<20; i++)
        for(j = 0; j<50; j++)
            for(k = 0; k<TCOUNT; k++)
                if(sample[i][j+k] == 0)
                    k += TCOUNT;
                cur_calc *= sample[i][j + k];
            if(cur_calc > max) 
            
...
cs



사실 이건 정확한 설계는 아니지만 C의 강력한 냅두기(?)식 방법을 이용한 것이다.

sample[][]에 들어가는 두 첨자 중에 뒤에 것인 j+k의 값이 최대 첨자인 50을 넘는다.

하지만! 그냥 다음 메모리를 읽어버리는 강력함! 사랑해요 C!

별다른 수정 없이 쉽게 답을 구했다.

마지막 줄에 쓰레기 메모리까지 읽어버리는 강력함이 있으므로 예외처리를 꼭 해주고!

물론 이 소스는 끝이 0이므로.. 안 해줬다는 전설이 전해진다.




728x90
반응형

'프로그래밍 > 알고리즘' 카테고리의 다른 글

[알고리즘] 플로이드 워샬 알고리즘  (5) 2015.07.11
Project Euler Problem16  (0) 2015.02.24
Project Euler Problem15  (0) 2015.02.17
Project Euler Problem10  (0) 2015.02.15
Project Euler Problem9  (0) 2015.02.15
Project Euler Problem5  (0) 2015.02.12
Project Euler Problem7  (0) 2015.02.05