책 이야기

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초 이상 걸리는 것을 보면 좀 더 빠른 방식으로 해결하는 방법이 있을 것 같다.

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

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

아래의 5x5 행렬에서, 오른쪽과 아래로만 갈 수 있을 때 왼쪽 위부터 오른쪽 아래까지 가는 최소 경로값은 굵은 붉은색으로 표시된 것과 같으며 2427이다.

80x80 행렬이 있는 31K 텍스트 파일 matrix.txt (우클릭하고 "다른 이름으로 링크 저장")을 오른쪽과 아래로만 갈 수 있을 때 , 왼쪽 위부터 오른쪽 아래까지 가는 최소경로 합계를 구하시오.

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

파일을 다루는 것에 익숙하지 않아서 파일을 열고, 내용을 읽고, 쉼표로 분리하고, 문자열을 숫자로 바꾸는 과정 하나하나를 다시 기억을 살려가며 해야 했다.

처음에는 단순하게 갈 수 있는 두 경우 중 작은 경우로 가는 것을 0,0과 79,79에서 시작하도록 해봤는데 오답이었다.

그래서, 생각해보니 방향이 제한적이기 때문에 조금은 단순하게 접근 가능할 것 같았다. 0,0부터 시작해서 차례로 이전과의 합계를 기록해 나가는 방식으로 하면, 79,79에 전체 합계가 기록되는 것이다. 각 자리에서는 자신에게 올 수 있는 2가지 경우의 합계 중 작은 것을 선택해 나가는 방식으로 하는 것이다.

이후 문제에까지 확장하여 적용하는 것은 쉽지 않을 것 같았는데, 일단 이 문제는 이 방식으로 해결 가능했다.

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is 1.41421356237309504880⋯, and the digital sum of the first one hundred decimal digits is 475.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

자연수의 제곱근이 정수가 아니면, 무리수가 된다. 이러한 제곱근의 소숫점은 반복되지 않으면서 무한하게 확장된다.

2의 제곱근은 1.41421356237309504880⋯이며, 소숫점 처음 100자리 숫자의 합은 475이다. 

100까지 자연수 중에서 제곱근이 무리수인 숫자의 소숫점 처음 100자리 숫자의 총합은 얼마인가?

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

처음에는 연분수 문제(문제 64)를 응용해서 간단하게 해결하려 했는데, 제곱근을 직접 계산하지 않으면 소숫점 이하에서 오차가 발생하는 문제가 있어, 제곱근을 손으로 계산하는 방법을 찾아 알고리즘으로 구현했다.

위 링크의 방법2에 왠만한 설명보다 자세하게 나와있기 때문에 코딩하는 데 그리 어렵지 않을 것이다. 프로그램으로 만드는 과정에서 break를 뺀다든지 하는 몇가지 오류가 있어 수정하는 데 시간은 좀 걸렸지만 재미있게 해결 가능한 문제였다.

The points P (x1, y1) and Q (x2, y2) are plotted at integer co-ordinates and are joined to the origin, O(0,0), to form ΔOPQ.

There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive; that is,
0 ≤ x1, y1, x2, y2 ≤ 2.

Given that 0 ≤ x1, y1, x2, y2 ≤ 50, how many right triangles can be formed?

좌표 P (x1, y1)과 Q (x2, y2)은 정수 좌표에 있으며, 시작점인 O(0, 0)과 연결되어 삼각형 ΔOPQ를 만든다.

좌표가 0과 2 사이일 때, 정확히 14개의 직각삼각형을 구할 수 있다.

0 ≤ x1, y1, x2, y2 ≤ 2.

0과 50 사이(0 ≤ x1, y1, x2, y2 ≤ 50)일 때 몇 개의 직각삼각형이 있는가?

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

O, P, Q 간의 관계를 잘 설정하면 반복문을 통해 만들어지는 삼각형을 피타고라스 정리(a²+b²=c²)를 이용해 직각삼각형인지 판단하면 되는 문제로 파악되었다.

O를 기준으로 P는 오른쪽, Q는 위쪽에 있는 좌표로 계산하기로 설정하였고, 반복문을 통해 P, Q가 가능한 모든 좌표에 대해 OP, OQ, PQ 거리를 구해서 피타고라스 정리를 만족하는 삼각형의 갯수를 구하였다.

P, Q의 한계를 조금 더 세밀하게 설정하면 속도가 더 빨라질 것 같았지만, 크게 늦지 않게 답을 구할 수 있어 만족하기로 했다.

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7.

    OOOOO
    OOOO   O
    OOO   OO
    OOO   O   O
    OO   OO   O
    OO   O   O   O
    O   O   O   O   O

Find the least value of n for which p(n) is divisible by one million.

n개의 동전을 서로 다른 방법으로 묶는 방법을 p(n)이라 하자. 예를 들어, 5개의 동전은 일곱 가지 다른 방법으로 묶을 수 있다. 따라서 p(5)=7이다.

    OOOOO
    OOOO   O
    OOO   OO
    OOO   O   O
    OO   OO   O
    OO   O   O   O
    O   O   O   O   O

p(n)이 1백만인 n의 최소값을 찾으시오.

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

동전으로 변형되어 있지만 문제 자체는 76번 문제과 동일한 알고리즘으로 해결 가능하다. 즉, 오일러의 오각수 정리 공식을 적용하면 된다. 76번과 차이점은, 76번은 2개 이상의 조합을 요구했기 때문에 전체 숫자에 해당하는 1을 빼야하지만(위 예시에서 동전 5개 묶음을 제외하므로 76번에서 p(5)=6), 이번 문제에서는 그 과정이 필요없다는 것이다.

한가지 고려할 사항은 동전 숫자에 상한선이 없으므로 76번 문제에서 적용했던 방법을 조금 변형시킬 필요가 있었다. 처음에는 상한선을 1만으로 했는데 답이 나오지 않아, 10만으로 바꾸고 나서 답을 구할 수 있었다.