그리드 게임 (grid game)
알고리즘 2# 문제풀이
알고리즘 공부 2번째 시간.
첫번째 시간에 버블 소팅을 해봤다.
https://brunch.co.kr/@babosamo/76
사실 문제 자체에 풀이가 있다고 해도 과언이 아니었다. 버블 소팅하시오 라고 했으니.
이제부터는 문제만 있고 그 해결 방법을 찾아가는 공부를 해보자.
문제
n x m 의 grid 가 있다.
[x,y] 쌍의 좌표가 k 개 주어진다.
좌표 x,y 는 모두 1 보다는 크다.
[0,0] 부터 주어지는 [x,y] 좌표 사이의 값을 모두 +1 증가 시킨다.
위의 방법을 k 번 반복한다.
좌표 값중 가장 큰 수의 개수를 구한다.
예제 값
k = 3
k0 = [2,3]
k1 = [5,4]
k2 = [2,2]
가장 높은 수 3의 개수는 4이다.
고민
문제에서 준 조건을 실행
문제에서 3개의 좌표를 주었다.
가장 단순하면서 뻔한 방법은 배열을 만들고 주어진 값이 원하는 만큼을 채워 넣는 것이다.
int [][] grid = {{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0}}
for 문으로 해당 영역을 +1 씩 증가 시켜주는 걸 K 번 반복한다. [2,3],[5,4], [2,2]
그 후 grid 에서 가장 높은 숫자를 구하고, 그 수의 개수를 구한다.
그런데 출제의 의도가 조건을 반복실행 하는 것은 아닐 것이다. (이렇게 풀면 50점은 받을 수 있을까?)
조금 더 생각해보자.
규칙 발견
주어진 값들을 그려보면 일정한 규칙이 발생함을 알 수 있다.
모든 영역은 [0,0] 에서 시작하고 있다. 그래서 주어진 좌표 K{n} 가 겹쳐지는 부분을 구할 수 있다.
그림으로 영역을 겹쳐서 그려보자.
즉, 문제가 원하는 건 [0,0] 부터 [2,2] 까지의 속하는 개수를 구하는 것이 된다.
구현
왼쪽 좌표, 하단 좌표는 0,0 으로 고정이다.
(만약 한쪽이 고정이 아니라면 교집합을 구하는 식은 더 복잡해 질것이다.)
겹쳐지는 부분의 교집합의 수를 구하면 된다.
교집합 X * 교집합 Y
가장 높은 수의 합 = min (x1, x2, x3 ...) * min (y1, y2, y3 ...)
구현 코드는 github 에 있습니다 ^^
https://github.com/babosamo/algorithm-grid-game
ps. fork & pull request 환영합니다.
ps2. 코드 지적, 다른 문제 풀이 더욱 환영합니다.
