Baekjoon 3085 사탕게임

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개 위치에 대해서 두 번씩 자리 변경을 한 후 각 행과 열에 대해서 연속 개수를 알아낸 후 최대값을 갱신해 출력한다.

 

알고리즘

1. 초기 보드 상태를 받는다.

2. 각 자리에 대해서 x + 1 , y / x , y + 1 위치와 변경 후 연속된 행 또는 열의 개수를 헤아린다.

3. 최대값을 출력한다.

 

소스코드