By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

    8 = (4 * (1 + 3)) / 2
    14 = 4 * (3 + 1 / 2)
    19 = 4 * (2 + 3) − 1
    36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

 

{1, 2, 3, 4}의 각 숫자를 한 번씩 사용하고, 4개 연산자(+, -, *, /)와 괄호를 사용하여, 서로 다른 정수를 구할 수 있다.

예를 들면 다음과 같다.

    8 = (4 * (1 + 3)) / 2
    14 = 4 * (3 + 1 / 2)
    19 = 4 * (2 + 3) − 1
    36 = 3 * 4 * (2 + 1)

주의할 것은 숫자를 연결하여 12+34로 계산하는 것은 허용되지 않는다.

{1, 2, 3, 4} 집합을 이용하여 31가지 다른 숫자를 구할 수 있고, 최대값은 36이다. 그리고, 1~28까지는 연속해서 구할 수 있다.

1부터 n까지 가장 긴 연속으로 숫자를 구할 수 있는 a<b<c<d인 숫자 4개를 구하고, 답안은 abcd 형태로 작성하라.,

--------------------------------------------------------------------------

 

몇가지 고민할 사항이 있어 나중에 해결했는데, 인터넷에서 누군가가 알려준 eval() 함수를 활용하면서 많은 부담을 덜 수 있었다.

 

연산자는 +,-,*,/의 4가지를 사용하는데, 예시에 있는 것처럼 연산자의 우선순위와 관계없이 계산하기 위하여 괄호를 이용해 인위적으로 순서를 지정할 필요가 있다. 연산자가 들어갈 곳은 3자리이므로 괄호를 통해 순서를 강제하는 것은 연산자의 순서를 1,2,3이라 할 때 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)의 6가지 경우가 있는데 이 중 (3,1,2)는 괄호를 통해서도 만들어낼 수 없는 경우이기 때문에 5가지 연산을 하게 만들면 된다.

 

4가지 숫자를 점차 커지는 순서로 만들고, 생성된 숫자 4개를 순열을 통해 다양한 순서를 만들고, 각 순서에 4가지 연산자 조합에 대해 5가지 연산을 해서, 결과가 양의 정수일 때 결과에 더하고, 모은 결과를 집합, 정렬을 통해 순서대로 배열해서 1부터 가장 긴 연속된 숫자가 있는 4가지 숫자 조합을 찾으면 된다.

 

위 경우 중 4가지 숫자를 커지는 순서로 만드는 데 반복문 4회, 순열 생성에 반복문 1회, 연산자를 3자리에 배열하는 데 반복문 3회를 해서 들여쓰기를 많이 하는 구조가 되었다.

 

그리고, 0으로 나누는 경우가 발생할 수 있으므로 exception을 사용하여 예외처리했는데, 개발툴인 Visual Studio Code가 익숙하지 않아서 exception을 무시하도록 설정하지 않아 처음에는 계속 F5를 눌러야 했다. 나중에 보니 Raised Exceptions을 Breakpoints로 설정하지 않도록 하는 옵션이 있어 결과를 빨리 볼 수 있었다.

 

 

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1  1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

 

숫자 체인은 각 자릿수를 더하여 새로운 숫자를 구하는 것을 끝날때까지 반복하면서 생성된다.

예를 들면 다음과 같다.

44 → 32 → 13 → 10 → 1  1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

따라서, 어떤 체인이든 1 또는 89가 되면 무한반복되면서 정체된다. 가장 놀라운 것은 모든 숫자는 결국 1 또는 89에 이른다는 것이다.

1천만 이하의 숫자 중에 89가 되는 숫자는 몇 개인가?

--------------------------------------------------------------------------

 

10자리수 이상은 자릿수별로 쪼개어서 제곱하고 더하는 과정을 반복하면서 89가 나오는 경우의 수를 더하도록 하면 되는 문제이다. 다만, 1천만 까지 계산하기를 요구했기 때문에 시간은 생각보다 엄청 많이 필요하게 된다.

 

그래도, 이 방법이 가장 정확한 방법이라 생각하고 속도를 조금 개선해보기 위해 제곱수를 매번 계산하지 않고 리스트를 만들어서 참조하게 했다. 그렇게 해서 256초가 245초로 조금 개선될 수 있었다.

 

문제를 해결한 후에, 인터넷을 검색해보니 동일한 순열(4666777과 6466777, 7664776)에 대해서는 한 번 계산한 결과를 이용하여 모든 체인을 계산하지 않도록 성능 개선이 가능하다고 되어 있다. 정말 세상은 넓고 해결방안은 다양하다는 것을 새삼 느끼게 된다.

 

 

A spider, S, sits in one corner of a cuboid room, measuring 6 by 5 by 3, and a fly, F, sits in the opposite corner. By travelling on the surfaces of the room the shortest "straight line" distance from S to F is 10 and the path is shown on the diagram.

However, there are up to three "shortest" path candidates for any given cuboid and the shortest route doesn't always have integer length.

It can be shown that there are exactly 2060 distinct cuboids, ignoring rotations, with integer dimensions, up to a maximum size of M by M by M, for which the shortest route has integer length when M = 100. This is the least value of M for which the number of solutions first exceeds two thousand; the number of solutions when M = 99 is 1975.

Find the least value of M such that the number of solutions first exceeds one million.

 

S라는 거미가 가로 6, 세로 5, 높이 3인 육면체 방의 구석에 있고, 반대쪽 코너에는 파리 F가 있다. 방 표면을 따라 S에서 F로 가는 가장 짧은 "직선" 거리는 10이고, 경로는 다음 그림과 같다.

그러나, 육면체 방에서는 3개의 최단 경로 후보가 있으며, 최단 경로는 정수길이가 아닐 수 있다.

회전을 무시하고, M=100일때 최대 가로 M(이하), 세로 M(이하), 높이 M(이하)이고 최단 경로가 정수인 육면체는 2060개가 있다. 이것은 M이 99일 때, 최단 경로가 정수인 육면체는 1975개 이며, 100일 때 처음으로 육면체의 수가 2천을 넘는다.

최단 경로가 정수인 육면체의 숫자가 1백만을 넘는 첫 M을 구하시오.

--------------------------------------------------------------------------

 

문제에서 회전을 무시한다고 했으므로, 경우의 수를 줄여서 계산해야 한다.

 

육면체에서 면의 길이 순서대로 a, b, c라고 한다면, 1<=a<=b<=c<=M이 된다. 이 조건에서, c**2+(a+b)**2의 제곱근이 자연수인 경우를 찾으면 된다.

 

a, b, c에 대한 3번의 반복문이 있어 실행시간이 필요하지만, 반복문을 구성할 때 위 조건에 따라 잘 정리한다면(b는 a값부터 반복문을 시작하고, a, b의 최대값은 c) 그렇게 어렵지 않게 구현 가능하다.

 

 

 

By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:

Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.

 

3x2 그리드에서 볼 수 있는 사각형을 주의깊게 세어 보면 18개가 나온다:

정확하게 2백만 개 사각형이 있는 그리드는 없지만, 2백만에 가장 가까운 그리드를 구하시오.

--------------------------------------------------------------------------

 

가로 세로로 나눠 생각해보면, 크기 3인 면(3x1 그리드)에 크기 1의 사각형은 3개, 크기 2의 사각형은 2개, 크기 3의 사각형은 1개 들어간다. 즉, (크기-사각형 크기+1)의 합계가 된다. 여기에 세로 길이를 고려하여 갯수를 구하면(가로x세로) 전체 사각형 갯수가 나온다.

 

이 문제에서는 2백만에 가장 가까운 그리드를 요구했는데, 2백만 보다 큰 지 작은 지 정확히 나오지 않아 두 경우를 모두 고려해야 했다.

 

그리고, 가로, 세로 크기에 한계를 정하지 않은 상태여서 그 부분을 미리 유추해야 할 필요가 있다. 가만히 보면 가로 합계x세로 합계가 형태이므로, (x(x+1)/2)*(y(y+1)/2)의 공식이 나오게 된다. 즉, x2*y2이므로 가로 세로가 100일 때 천만 이상의 사각형이 나오게 되므로, 여유를 주고 반복문을 통해 2백만에 근접한 값을 구하게 했다.

 

공식을 생각하기 전에 사각형 갯수를 구하는 반복문을 만들어서 그대로 썼는데, 간단한 공식으로 구할 것을 사각형 크기별로 합계를 모두 구하게 해서, 실행 속도를 손해보게 된 것 같다.

NOTE: This problem is a more challenging version of Problem 81.

The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

Find the minimal path sum from the left column to the right column in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.

 

주의: 이 문제는 문제81 보다 더 어렵다.

첫번째 열의 원소에서 시작해서 마지막 열에서 끝나며 위, 아래, 오른쪽으로만 움직일 때 아래의 5x5 행렬에서 최소 경로는 붉은 색으로 굵게 표시되어 있으며 합계는 994이다.

80x80 행렬이 있는 31K 텍스트 파일 matrix.txt (우클릭 하고 "다른 이름으로 링크 저장")의 첫번째 열에서 마지막 열까지 이동할 때 최소 경로의 합계를 구하시오.

--------------------------------------------------------------------------

 

81번 문제를 해결한 방법을 그대로 사용할 수는 없었지만, 그 방법을 가져와서 반복을 통해 해결했다. 81번 문제에서는 답을 구할 자리가 행렬 전체의 마지막 자리(80, 80)이지만, 이번 문제에서는 마지막 열(x,80) 모두가 답이 되는 후보이기 때문에 마지막 열 각 행을 기준으로 최소 경로의 값을 구하는 방식으로 접근했다..

 

위 예시를 기준으로 예를 들면, 2번째 열, 2번째 행의 최소값 후보는 1번째 열 각 행에서 시작한 5개 경로의 값 900(131+673+96), 297(201+96), 1529(630+803+96), 2135(537+699+83+96), 3135(805+732+699+803+96) 중 가장 작은 297이 된다. 이 예시에서 131다음에 201로는 왜 안가고 673으로만 가는지 의문이 들 수 있는데, 이 경우 201에서 시작한 경우보다는 무조건 크기 때문에 최소값이 될 수 없다고 생각해서 배제했다.

 

이런 식으로 각 열의 최소값을 2번째 열부터 마지막 열까지 구하고, 마지막 열 각 행의 최소 경로 값 중에서 제일 작은 값을 찾으면 된다. 그런데, 다중 반복문을 실행하느라 시간이 7초 이상 걸리는 것을 보면 좀 더 빠른 방식으로 해결하는 방법이 있을 것 같다.

+ Recent posts