Project Euler - 문제 8번

Largest product in a series

Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.

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

 문제 8번 : 다음의 1000자리 숫자 속에서 가장 큰 다섯 숫자의 연속적인 곱을 찾으시오.

---

 아... 처음에 이걸 보고 막막해지더군요. 이걸 어떻게 입력을 받아야하나... 싶었는데, 일단 string으로 받은 다음에 각각의 숫자를 string.at(i)로 꺼낸 다음, int 배열에 저장하는 방법으로 해결했습니다. 이렇게 되면, string에서 나온 숫자들은 배열에 들어갈 때에 숫자로 들어가지 못하고 ASCII 코드로 들어가게 되는데, 0부터 9까지의 숫자들이기 때문에 그냥 ASCII 코드에서 48만큼 빼주면 정확히 그 숫자와 같게 됩니다. 일종의 편법이지요.

 그래서 이를 통해 길이 1000짜리 배열에 모조리 저장하고 연속적으로 5개씩 곱하면서 가장 큰 곱을 찾는 방법을 쓰는데, 계산 속도를 빠르게 하기 위해서 0을 만날 경우에는 5칸씩 건너뛰는 방법을 사용했습니다. 어차피 0이 한번 나오기 시작하면 5번동안 0이 걸리면서 모든 결과가 0이 되기 때문에 무의미하기 때문이지요.

#include <iostream>
#include "time.h"

using namespace std;

int main()
{
 clock_t start = clock();
 
 string numbers;
 numbers = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
 int num[numbers.length()];
 
 for(int i = 0; i < numbers.length(); i++)
  num[i] = numbers.at(i) - 48;  // ASCII code to int
 
 int result = 0;
 for(int i = 0; i < numbers.length()-5; i++)
 {
  int temp = num[i];
  for(int j = 1; j < 5; j++)
  {
   temp = temp * num[i+j];
   if(temp == 0)
   {
    i += j;
    break;
   }
   else if(temp > result)
    result = temp;
  }
 }
 
 clock_t end = clock();
    cout << "Result : " << result << endl;
    cout << "Time : " << (long double)(end-start)/CLOCKS_PER_SEC;
    return 0;
}

 이렇게 해서 결과를 구하면 바로 답이 나옵니다.

 결과는 정답! 중간에 실수했는데도 정답이 나와서 아무 생각없이 맞은 코드인줄 알았는데, 나중에 확인하고 고쳤네요.