티스토리 뷰

Project Euler

프로젝트 오일러

 

Problem 8

특정 수열에서 연속된 5개의 숫자를 곱했을 때 가장 큰 수는?


다음은 연속된 1000자리 숫자입니다 (읽기 좋게 50자리씩 잘라놓음).


73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450


여기서 붉게 표시된 71112의 경우 7, 1, 1, 1, 2 각 숫자를 모두 곱하면 14가 됩니다.

이런 식으로 맨 처음 (7 × 3 × 1 × 6 × 7 = 882) 부터 맨 끝 (6 × 3 × 4 × 5 × 0 = 0) 까지 5자리 숫자들의 곱을 구할 수 있습니다.

이렇게 구할 수 있는 5자리 숫자의 곱 중에서 가장 큰 값은 얼마입니까?


Hint


힌트1.

첫번째 줄의 앞 10자리 숫자로 예를 들면 [ 7316717653 ]


여기서 말하는 연속된 5개의 숫자는

73167, 17653 이게 아니고

73167, 31671, 16717, ... 이런식으로 연속된 숫자를 말하는 것입니다.

인덱스로 말하면


01234, 12345, 23456, ... 이걸 뜻하는 것!


힌트2.

0은 곱하면 0이 되버리므로 처리할 필요가 없다.


Answer


public class euler08 {

public static void main(String[] args){
String mainNums =
"73167176531330624919225119674426574742355349194934" +
"96983520312774506326239578318016984801869478851843" +
"85861560789112949495459501737958331952853208805511" +
"12540698747158523863050715693290963295227443043557" +
"66896648950445244523161731856403098711121722383113" +
"62229893423380308135336276614282806444486645238749" +
"30358907296290491560440772390713810515859307960866" +
"70172427121883998797908792274921901699720888093776" +
"65727333001053367881220235421809751254540594752243" +
"52584907711670556013604839586446706324415722155397" +
"53697817977846174064955149290862569321978468622482" +
"83972241375657056057490261407972968652414535100474" +
"82166370484403199890008895243450658541227588666881" +
"16427171479924442928230863465674813919123162824586" +
"17866458359124566529476545682848912883142607690042" +
"24219022671055626321111109370544217506941658960408" +
"07198403850962455444362981230987879927244284909188" +
"84580156166097919133875499200524063689912560717606" +
"05886116467109405077541002256983155200055935729725" +
"71636269561882670428252483600823257530420752963450";

int index = 0;
int MAX = 0;

// mainNums의 첫번째 문자의 인덱스를 0, 마지막 문자의 인덱스를 999라고 한다면
// 마지막으로 체크해야 하는 연속된 5자리 숫자의 인덱스는
// 995, 996, 997, 998, 999 이다.
// 그러면 index는 1~995까지 실행되어야 한다.
// 그래서 조건은 index < 996
// mainNumbers.length() - 4 = 1000 - 4 = 996
while(index < mainNums.length()-4){
int multiNum = 1;

for(int i=index; i<index+5; i++){
//char로 얻어온 숫자를 int로 바꾼다.
int integerNum = mainNums.charAt(i) - 48;
System.out.println("i : "+i);

if(integerNum == 0){
// 0이 나오면 0이 포함된 계산을 하지 않도록 4를 더하고 빠져나간다.
// 5가 아닌 4를 더하는 이유는 while문 마지막에서 1을 항상 더하고 있기 때문.
index += 4;
break;
}
multiNum *= integerNum;
}

if(multiNum > MAX){
MAX = multiNum;
}

index += 1;
}

System.out.println(MAX);
}
}








댓글
댓글쓰기 폼
공지사항
Total
37,833
Today
31
Yesterday
37
링크
TAG
more
«   2018/05   »
    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    
글 보관함