Baekjoon 3085 사탕게임
2019. 8. 21.
Link https://www.acmicpc.net/problem/3085 소스결과 1988 KB / 60 ms 출처 Baekjoon 언어 C++ 17 분류 Brute Force 설명 사탕을 가까운 사탕과 위치를 바꿨을 때 먹을 수 있는 사탕의 최대 값을 구하여라. 일단 보드의 최대 크기가 50밖에 안된다. 또한 모든 자리에 대해서 상, 하, 좌, 우 전부 탐색하는 것이 아닌 하, 우 만 검색하면 된다. 검색하는 위치가 그리디 하게 진행이 가능한 이유는 x 또는 y위치에 대해서 -1 위치와 바꾸는 것은 x-1 또는 y-1의 위치에서 +1 위치로 바꾸는 결과와 똑같기 때문이다. 따라서 최대 2500개 위치에 대해서 두 번씩 자리 변경을 한 후 각 행과 열에 대해서 연속 개수를 알아낸 후 최대값을 갱신해 출..
