나의 논리
3개의 돌의 갯수를 분배해서 3개의 돌그룹의 갯수를 맞추는 문제이다.
3개의 돌그룹들이 가지는 숫자들 ,예를 들면 a,b,c 들이 한 상태이고 문제에 제시된 연산을 1번 한 상태를 다른 상태라고 치자. 한 상태에서 다른 상태로 바뀌는 로직을 BFS로 풀려고 했다.
우선 3개의 변수를 다루므로 튜플을 가지고 튜플들의 상태를 큐에 넣기로 했다.
3차원 bool 타입의 배열로 check 배열을 만들어 a,b,c의 상태들을 확인해 방문처리를 하고 큐에서 이미 연산이 된 돌 그룹 a,b,c가 나오면 이미 방문했으므로 다음 연산으로 넘어간다.
조금 생각해봤을때 돌 그룹 a,b,c가 나왔을때, (a,b,c), ( a,c,b) ,(b,a,c)…등 모두 같은 돌 그룹들이다.
이 부분을 개선하고자 배열에 담은뒤, 정렬 한 후 check 배열에서 확인 했다.
그러나 a,b,c가 최대 500이 될 수 있으므로 예를들어 499,500 둘 중 연산을 하면, 998, 1이 된다.
한 돌그룹이 가질 수 있는 수의 범위가 1<= 돌 <= 약 1000 인데 3차원 배열로 하니까 메모리가 1GB를 차지해버려서 메모리 초과가 떳다.
정답논리
핵심적인 내용은 다음과 같다.
- 돌 그룹을 모두 합한 전체 갯수는 변하지 않는다.
- 따라서 두 돌그룹만 선택하면 나머지 하나는 결정된다.
- 3차원 배열대신 2차원 배열로 대신 할 수 있다.
- 돌 그룹간의 순서는 상관없기 때문이 이 방식으로 (a,b,c) , (a,c,b) .. 등과 같은 순서에 대한 처리가 가능하다.
(1,2,3)을 모두 번갈아가며 비교하는 방법이 인상적이었다.
브루트 포스방식으로 하면 (1,2), (1,3), (2,3)에 대해 a가 b보다 큰 경우, 작은 경우를 처리해야되서 총 6가지의 연산을 생각했었는데 배열 {1,1,2} , {2,3,3}로 저장하고 각 배열에서 하나씩 꺼내서 연산을 처리하면 3분의 1로 코드가 준다.
int nx = min(min(a, b), c);
int ny = max(max(a, b), c);그리고 두 수가 정해지면 나머지 하나는 자동으로 정해지는 성질로 덕분에
제일 큰 수와 제일 작은 수를 구해 이미 나온 패턴인지 아닌지 check 배열로 검사한다
