백준 17127) 벚꽃이 정보섬에 피어난 이유

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

17127번: 벚꽃이 정보섬에 피어난 이유

 

문제

정보섬에 벚꽃이 피어났다!

정보섬에 만발한 꽃송이들을 본 욱제는 한 가지 좋은 생각을 떠올렸다. 아래와 같은 네 개의 푯말을 준비해서 정보섬의 꽃밭에 세우는 것이다.

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

정보섬의 1층 꽃밭에는 총 N개의 벚나무가 일렬로 늘어서 있다. 각 벚나무에는 늘어선 순서대로 A1, A2, ..., AN개의 벚꽃이 피어나 있다. 욱제는 이 벚나무를 총 네 개의 그룹으로 나누어 각 그룹을 대표하도록 푯말을 세웠다.

이 그룹을 나눈 데에는 특별한 기준이 있다. 그룹 [i, j]의 벚꽃 개수들의 곱 Pi,j = Ai × Ai+1 × ... × Aj-1 × Aj (i ≤ j)가 네 개 있을 때, 네 개의 P의 합이 최대가 되도록 나누었다. 다시 말해, 그룹 내의 벚꽃 개수를 모두 곱하고, 그렇게 곱해진 값 네 개를 모두 더한 값이 최대가 되도록 나누었다. 욱제는 연속된 순서의 나무들만 하나의 그룹으로 묶고, 모든 나무들을 빠짐없이 정확히 하나의 그룹에 포함시켰다. 또한 하나의 그룹에는 반드시 하나 이상의 나무가 포함되었다.

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

힘든 하루를 마치고 집으로 돌아가던 당신은 정보섬 1층에 만발한 꽃송이와 푯말을 보았다. 그리고 갑자기 최대화 된 네 개의 P의 합이 얼마인지 궁금해졌다.

얼마일까?

 

입력

첫째 줄에 벚나무의 개수 N이 주어진다. (4 ≤ N ≤ 10)

둘째 줄에 N개의 나무에 피어난 벚꽃의 개수 Ai가 순서대로 주어진다. (1 ≤ Ai ≤ 5)

출력

얼마일까?

예제 입력

7

2 5 3 1 4 2 3

예제 출력

67

 

 

---

 

 

생각보다 시간을 많이 투자한 문제였다.

 

'예제 입력'을 확인하고 바로 이해는 됐지만 구현으로 들어가는 과정이 복잡하게만 느껴졌는데,

0번째부터 차례대로 최대 묶음 수를 곱한 값을

max 변수와 비교해서 저장하면 되겠지만,

나머지 원소들을 어떻게 더해야 할지 고민을 많이 했다.

 

문제에서 제시한 방법과 같이 7개의 원소 중에 1~4 원소를 묶은 값이 max라면,

나머지 원소(0,5,6) 들을 어떻게 추출해서 max 값에 더해줄지 생각해봤지만 잘 떠오르지 않았다.

 

 

 

일단 규칙을 찾아보려 했다.

 

 

7일 때

 

1 2 3 4 5 6 7

1 2 3 4 5 6 7

1 2 3 4 5 6 7

1 2 3 4 5 6 7

최대화된 4개의 합이라고 나와있으므로 위와 같이 묶어준다면,

7-3 = 4 개를 4번 실시한다.

 

5일 때

 

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

5-3 = 2개를 4번 실시한다.

 

 

이렇게 규칙을 찾게 되면서 항상 n-3 개를 묶고, 4번을 반복시키면 되겠구나 까지 접근할 수 있다.

이 때 주의할 점은, i 가 0 부터 시작한다면, i 부터 n-3 + i 번 까지 최댓값을 만들어내야 한다!

왜냐하면 i가 1씩 커질수록 위에서 본 규칙처럼 뒤로 한칸씩 가야 되니 말이다.

 

 

이제 그렇다면 최댓값에 포함되지 않는 애들은 어떻게 해야 할까?

구현과 문자열에서 BooleanArray로 check하는 기법을 몇 번 풀어본 게 기억나서

해당 문제에도 접목시켜봤다.

 

 

최댓값을 만들기 위해서 원소 하나하나를 곱해줄 때, 그 원소의 인덱스 값을 boolean 배열에 true로 저장한다.

반복문을 빠져나오면 다시 반복문을 열어서 0부터 n까지 false인 원소를 찾는다.

만약 false라면 최댓값 연산에 포함되지 않은 인덱스이므로, 최댓값에 마저 더해준다.

 

 

처음에 max = 0 으로 초기화한 후에,

특정 변수에 위의 연산 값을 대입하고

max 값과 비교해서 특정 변수가 max값보다 크다면

max 변수에 특정 변수 값을 저장한다.

 

 

 

 

전체 코드는 다음과 같다.

 

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val arr = readLine().split(" ").map { it.toInt() }
    val check = BooleanArray(n)
    var max = 0
    for(i in 0 until 4) {
        var data = 1
        for (j in  i until n - 3 + i) {
            data *= arr[j]
            check[j] = true
        }

        for(k in 0 until n) {
            if(!check[k]) data += arr[k]

        }
        if(data > max) max = data
        repeat(n) {
            if(check[it]) check[it] = false
        }
    }
    println(max)
}