[BOJ - 12886] 돌 그룹

https://www.acmicpc.net/problem/12886

12886번: 돌 그룹

문제 논리자체는 딱.. 그 세자리 숫자에 관한 Memoization을 통해 BFS를 써주면되겠다!

라는 생각이들지만, 이러한 생각은 문제의 조건에 부합하지않는다.

일단 값의 합과, 차를 구하는과정을 배열의 index에 매칭시켜주는 과정에서

index를 매칭할수있는 최대값이 1500정도에 가깝다.

그러나, 1500 x 1500 x 1500은 정말 너무 큰 숫자다.

대략..3기가? 정도넘을거같은데, 터무니 없이 큰 메모리이므로

다른방식을 생각해보자.

 

나는, Memoization으로 세가지 를 한번에 고려하는 방식보다는 두가지씩 비교해나가면서

그 비교된것들을 토대로 답을 도출하는 과정으로 문제를 해결했다.

예를들어, X,Y,Z 이렇게 세가지 숫자가 있다면

X, Y 을 첫번째로 비교하고, (X,Z) , (Y,Z) 순서대로 비교해나갔다.

-> 비교해 나가면서 첨부된 사용되지않은 X,Y,Z 에 대한것을 계속해서 큐로 생성해나감

 

이방식대로해서 시간이 더걸리는지는 모르겠으나, 세가지 다비교할수없다면

두가지씩 비교해나가는 관점은 사실 보다 직관적인 방법이아닐까?