-
백준(BOJ) 3085번 사탕 게임알고리즘 풀이/백준(Boj) 2019. 10. 27. 02:05
문제 : https://www.acmicpc.net/problem/3085
3085번: 사탕 게임
문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하
www.acmicpc.net
풀이 :
상하좌우 바꿀 수 있지만 위쪽이나 왼쪽 교환은 이전 칸에 오른쪽이나 아래쪽 교환으로 구할 수 있기 때문에
아래, 오른쪽만 교환해주면 된다. 오른쪽 교환후에 각 행과 열에 최댓값을 구하고 왼쪽 교환 후 각 행과 열에 최댓값을
구하자. N이 50으로 작기 때문에 N*N*2번 교환 그 교환안에서 N*N번 일어나므로 시간 안에 해결 가능하다.
코드 ( C++ )
'알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 16928번 뱀과 사다리 게임 (31) 2019.11.01 백준(BOJ) 17070번 파이프 옮기기 1 (31) 2019.10.31 백준(BOJ) 1937번 욕심쟁이 판다 (31) 2019.10.27 백준(BOJ) 2169번 로봇 조종하기 (3) 2019.10.27 백준(BOJ) 14225번 부분수열의 합 (31) 2019.10.25