algo-auth

Description

Category: Misc/Coding

Source: Codegate 2019 Quals.

Points: 7.0

Author: Jisoon Park(js00n.park)

Description:

I like an algorithm

nc 110.10.147.104 15712
nc 110.10.147.109 15712

Write-up

주어진 사이트에 접속해보면 minimal path sum을 구하는 문제임을 알 수 있다.

인터넷에서 minimal path sum을 푸는 문제를 찾아보면 여러 코드를 확인할 수 있는데, Euler 81 관련 알고리즘들이 많이 보이지만 이는 첫 모퉁이에서 마지막 모퉁이까지의 minimal sum을 구하는 문제로 첫 열의 임의의 위치에서 마지막 열의 임의의 위치로 가야하는 이 문제와는 조금 다르다.

Euler 81 코드를 살짝 변형해서 풀까 했었지만, 코드 분석이 쉽지 않아서ㅜㅠ 그냥 새로 구현했다.

(모 export 분은 5분이면 풀겠다고 했지만 나는.. 구현에 약간 시간이 걸렸으나, 결국 풀 수 있었다.)

구현 아이디어는 간단한데, 한 열을 기준으로 임의의 각 위치에서 마지막 열로 빠져나가기 까지의 minimal sum을 계속 업데이트하는 방법이었다.

문제에서 예제로 주어진 matrix(=MA)를 반시계방향으로 90도 회전하면 아래와 같은 모양이 된다.
(python에서 열을 다루는게 불편해서 회전한 후 풀었다.)

99	99	99	99	1	99	99
99	99	99	99	1	1	1
99	99	99	99	99	99	1
99	99	99	99	1	1	1
99	99	99	99	1	99	99
99	99	99	99	1	1	99
99	99	99	99	99	1	99

위의 MA를 기반으로 새로운 matrix(=MB)를 만든다. 일단, 첫번째 줄은 그대로 가져오고 두번째 줄은 각각 바로 위의 셀과 합한 값으로 채운다.

99	99	99	99	1	99	99
198	198	198	198	2	100	100

그 다음, 두번째 줄의 각 셀을 훑는데, n번째 셀의 값을 matrix에 따라 MA[n] 또는 MB[n]이라고 하면, MB[n] = min(MB[n], MA[n] + MB[n - 1], MA[n] + MB[n + 1])으로 업데이트한다.

이렇게 마지막까지 순회를 한 후, 순회 중에 더이상 업데이트가 일어나지 않을 때까지 순회를 반복하면 MB의 두번째 줄은 아래와 같이 업데이트가 된다.

99	99	99	99	1	99	99
198	198	198	101	2	3	4

두번째 줄과 같은 방식으로 나머지 줄들을 모두 업데이트 하면 아래와 같은 MB를 얻을 수 있다.

99	99	99	99	1	99	99
198	198	198	101	2	3	4
297	297	297	200	101	102	5
396	305	206	107	8	7	6
405	306	207	108	9	106	105
406	307	208	109	10	11	110
505	406	307	208	109	12	111

주어진 matrix MA에 대한 minimal path sum은 마지막줄에서 가장 작은 값인 12가 된다.

100번을 연속으로 문제를 풀면 flag를 줄 것이라고 생각했는데, 엉뚱하게도 지금까지 제출한 답이 flag라고 한다. (위 캡쳐는 답들을 모으도록 수정한 후의 실행 결과)

문제를 풀 때마다 그 값들을 모으도록 코드를 수정해서 다시 돌렸더니 100글자 짜리 의미없어보이는 문자열을 획득할 수 있었고, expert님의 도움을 받아 다시 base64 디코딩을 하여 flag를 얻었다.

Flag : **g00ooOOd_j0B!!!__uncomfort4ble_s3curity__is__n0t__4__security!!!!!**