02.04. 사탕게임[Brute-force Search][백준 3085]

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

Algorithm classification : Brute-force Search

 

02.04.1. Problem

Given an arbitrary sequence of n integers. We try to find the largest sum of possible sums by selecting several consecutive numbers among them. However, more than one number must be selected. For example, given the sequence 10, -4, 3, 1, 5, 6, -35, 12, 21, -1. Here, the correct answer is 33, which is 12 + 21.

 

02.04.2. Input limit

The first line is given an integer n (1 ≤ n ≤ 100,000) and the second line is a sequence of n integers. number is an integer greater than or equal to -1,000 and less than or equal to 1,000.

 

02.04.3. Output

첫째 줄에 답을 출력한다.

 

02.04.4. Solution

지도가 50by50이고, 인접한 칸끼리 바꿀 수 있는 경우의 수를 계산해보면 50*49*2번 정도일 겁니다. *2는 위아래로 바꾸느냐 양옆으로 바꾸느냐를 고려한 것입니다. 뭐 이중 for문으로 해보면 되겠죠.

 

check하는 함수와 뒤바꾸는 logic만 잘 만들면 될 것 같습니다. 그리고 뒤바꾸고 나서 다른 케이스를 시도해보기 전에 원래대로 되돌려야 한다는 것을 잊지마세요.

int check(char data0[][50], int max0){
	int i, j, count, k;
	for(i = 0; i < n; i++){
		for(j = 0; j < n; j++){
			count = 1;
			for(k = 1; i+k < n, data0[i][j] == data0[i+k][j]; k++){
				count++;max0 = max(max0, count);
			}
			
			count = 1;
			for(k = 1; j+k < n, data0[i][j] == data0[i][j+k]; k++){
				count++;max0 = max(max0, count);
			}
			
		}
	}
	return max0;
}

	for(i = 0; i < n ; i++){
		for(j = 0; j < n; j++){
			if(i+1 < n && data0[i][j] != data0[i+1][j]){
				temp = data0[i][j];
				data0[i][j] = data0[i+1][j];
				data0[i+1][j] = temp;
				max0 = check(data0, max0);
				temp = data0[i][j];
				data0[i][j] = data0[i+1][j];
				data0[i+1][j] = temp;
			}
			if(j+1 < n && data0[i][j] != data0[i][j+1]){
				temp = data0[i][j];
				data0[i][j] = data0[i][j+1];
				data0[i][j+1] = temp;
				max0 = check(data0, max0);
				temp = data0[i][j];
				data0[i][j] = data0[i][j+1];
				data0[i][j+1] = temp;
			}
		}
	}