[백준 / BOJ] 10885 수열의 장인

문제

출처 : https://www.acmicpc.net/problem/10885

10885번: 수열의 장인

길이 N의 수열이 주어진다.

수열의 각 수는 -2, -1, 0, 1 2로 이루어져있으며, i번째 수열을 Ai, j번째 수열을 Bj라 하자. (i <= j)

이때, 임의의 범위 i,j를 선택하여 Ai ~ Aj에 포함되는 모든 수를 곱했을때 최댓값이 되도록 i,j를 설정하고, 그때의 최댓값을 출력하는 문제였다.

---

풀이

아이디어는 금방 나왔으나, 푸는데 시간이 좀 걸린문제였다.

 

우선, 입력으로 주어질수있는 수를 확인해보면,

 

-2, -1, 0, 1, 2 

 

이렇게 총 5가지 이다.

이때, 곱하기라는 조건을 통해 유추할수있는 힌트가 몇가지 있었는데,

 

1. 양의 정수는 항상곱해줘도 손해보지않는다.

(양의정수는 곱해도 항상 이득이거나 제자리임)

 

2. 음의 정수는 음의 정수가 짝수번 나올때, 즉, 음의 정수 % 2 == 0일때는 항상 곱해줘도 손해보지않는다.

(음수 * 음수는 양수이므로 음의 정수가 짝수번 나온경우에는 항상 이득이다.)

 

3. 0의 경우 항상 0으로 초기화 된다.

- 수열 중간에 0이 나온다면 0을 기준으로 0 이전, 0 이후 수열은 서로 상관없는 다른 수열이라고 생각해도 무방하다.

 

위의 조건을 토대로 문제를 푸는 방법을 생각해보면 다음과 같음을 알수있다.

- 음의 정수를 짝수개 선택하면서 절댓값 2의 개수를 최대한 많이 만드는 범위(혹은 2의 갯수)를 구하는 것

- 수열에 현재까지 포함된 음의 정수가 짝수라면 수열의 길이를 최대한 늘리는것이 항상 이득이다.(중간에 0이 끼어있는경우 제외)

 

구현아이디어를 떠올리는게 좀 어려웠는데,

이 문제는 모듈러 연산을 진행하며 최댓값을 비교해주는 방식으로는 풀 수 없다.

예를들어 설명하자면, 

위 조건 3번에서 0을 기준으로 다른 수열이라고 생각한다고 했다.

 

0을기준으로 앞에 있는 수열은 2^64이고, 뒤에있는 수열은 2^128 이라고 가정해보자.

 

우리는 상식적으로 0을 기준으로 뒤에있는 수열이 더 큰수임을 알수있다.

하지만, 모듈러 연산을 진행한 후에도 과연 그럴까?

 

- 2^64 % 1000000007 = 582,344,008

- 2^128 % 1000000007 = 279,632,277

 

따라서, 모듈러 연산을 하지않고, 범위를 찾아줘야했는데, 나는 약간의 트릭을 이용해서,  "2"의 갯수를 카운팅해줬다.

 

이 문제에서 입력되는 수의 범위는 -2 <= num <= 2 이고, 답에 유효한 변경을 일으키는 수는 -2, 2 둘밖에없다.

-2인경우와, 2인경우를 적절히 처리해주며 카운팅해주고, 2가 가장 많이 나온경우에서 답을 구해주면된다.

 

구현

구현을 위해, 우선, 변수 3개를 선언해준다. 각 변수가 하는 역할은 다음과 같다.

block : 음수가 나온 횟수를 카운팅 한다. block이 2의 배수가 아니라면, num을 전부 곱했을때 음수가 나올것이고 아니라면 항상 양수다.

num : 절댓값 2가 나온횟수를 카운팅한다. block 변수에서 음수처리를 따로 해주기 때문에, 음수값에 대해 신경쓰지 않아도 된다.

oldestOddCount : 이 변수를 이해하는게 중요하다. oldestOddCount는 가장 처음 음수가 나왔을때의 절댓값 2의 갯수를 카운팅 한 값을 저장한다. 이 변수가 필요한 이유는 다음과 같다.

예제가

1

5

-1 2 -1 2 -2

처럼 주어질경우, 우리는 2가지 선택지를 가질수있다.

(수열의 길이를 항상 최대한으로 늘리는게 이득임을 알고있으므로 선택지는 2가지밖에없다.)

1) idx = 0 ~ idx = 3

2) idx = 1 ~ idx = 4

당연하게 2)가 더 크지만, 우리의 알고리즘으로는 이를 확인할 방법이 없기 때문에, oldestOddCount  변수를 따로 두어 체크를 해주는것이다.

 

자세한 구현은 소스코드를 확인하자.

	private long getLargestNum(int[] arr, int[] negArr){
		int block = 0;
		int oldestOddCount = -1;
		int num = 0;
		int maximum = 0;
		for(int i = 0; i < N; i++){
			if(arr[i] == 0){
				if(block == 1) maximum = Math.max(num - oldestOddCount, maximum);
				block = 0;
				num = 0;
				oldestOddCount = -1;
				continue;
			}
			num += ((arr[i] % 2 == 0) ? 1 : 0);
			block += ((arr[i] < 0) ? 1 : 0);
			if(block == 2) block = 0;
			if(block == 0) maximum = Math.max(num, maximum);
			if(i < N-1 && block == 1 && oldestOddCount == -1) oldestOddCount = num;
		}
		if(arr[N-1] != 0 && block == 1 && oldestOddCount != -1) maximum = Math.max(num - oldestOddCount, maximum);
		long ret = 1L;
		if(maximum == 0){
			int cntNegativeOne = 0;
			for(int i = 0; i < N; i++){
				if(arr[i] == 1) return 1;
				if(arr[i] == 0) cntNegativeOne = 0;
				if(arr[i] == -1) cntNegativeOne++;
				if(cntNegativeOne == 2) return 1;
			}
			return 0;
		}
		while(maximum > 0){
			ret = ((ret % rem) * (2 % rem)) % rem;
			maximum -= 1;
		}
		return ret % rem;
	}

 

시간복잡도는(특정한 테케 예외처리하는 부분을 제외하면)

O(N)이 나온다.

 

반례

문제를 풀며 틀리기 쉬운 반례를 만들어 적어놨다.

https://www.acmicpc.net/board/view/74940

글 읽기 - 틀리기 쉬운 반례 모음

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/10885%20%EC%88%98%EC%97%B4%EC%9D%98%20%EC%9E%A5%EC%9D%B8/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃