백준 1239번
https://www.acmicpc.net/problem/1239

문제

---

생각하기

---

• 완전탐색 기반, 백트래킹, 투포인터 문제이다.

동작

먼저 50과 51이 있으면 만들어지는 답은 고정적이다.
50이 하나라도 있으면 중심을 지나는 선은 하나가 최대이고, 51 이상이 있으면 중심을 지나는 선은 있을 수 없다.

    arr.forEach {
        if (it >= 51) {
            sb.append(0)
            return sb.toString()
        } else if (it == 50) {
            sb.append(1)
            return sb.toString()
        }
    }
    

다음은 만들어진 N개의 숫자에서 조합을 찾아야 한다.

예시가

6
1 48 1 1 48 1

이면 답은 3이 되는데

수를 1 1 48 1 1 48형식으로 나열할 경우

1 1 48
1 48 1
48 1 1로 해서

50을 총 3가지 경우로 만들 수 있기 때문이다.

그래서 DFS를 통해서 먼저 수열을 만들고,

private fun DFS(idx: Int) {
    if (idx == N) {
        twoPointer(0, 1, comb[0], 0)
        return
    }

    for (i in 0 until N) {
        if (isVisited[i]) continue
        isVisited[i] = true
        comb[idx] = arr[i]
        DFS(idx + 1)
        isVisited[i] = false
    }
} // End of DFS()

그 후 투 포인터를 통해서 수열에서 50이 만들어지는 경우의 수를 확인한다.
그리고 그중 가장 만들어진 경우의 수 최댓값이 정답이 된다.

private fun twoPointer(left: Int, right: Int, sum: Int, count: Int): Int {
    var count = count
    var sum = sum
    var left = left
    var right = right
    if (right == N) {
        max = Math.max(max, count)
        return max
    }

    if (sum == 50) {
        count++
        sum += comb[right++]
        sum -= comb[left++]
    } else if (sum > 50) {
        sum -= comb[left++]
    } else {
        sum += comb[right++]
    }

    return twoPointer(left, right, sum, count)
} // End of twoPointer()

결과

코드

---

Kotlin

import java.io.BufferedReader
import java.io.File
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private var max = 0
private lateinit var arr: IntArray
private lateinit var comb: IntArray
private lateinit var isVisited: BooleanArray

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    arr.forEach {
        if (it >= 51) {
            sb.append(0)
            return sb.toString()
        } else if (it == 50) {
            sb.append(1)
            return sb.toString()
        }
    }

    max = 0
    isVisited = BooleanArray(N)
    comb = IntArray(N)
    DFS(0)

    sb.append(max)
    return sb.toString()
} // End of solve()

private fun DFS(idx: Int) {
    if (idx == N) {
        twoPointer(0, 1, comb[0], 0)
        return
    }

    for (i in 0 until N) {
        if (isVisited[i]) continue
        isVisited[i] = true
        comb[idx] = arr[i]
        DFS(idx + 1)
        isVisited[i] = false
    }
} // End of DFS()

private fun twoPointer(left: Int, right: Int, sum: Int, count: Int): Int {
    var count = count
    var sum = sum
    var left = left
    var right = right
    if (right == N) {
        max = Math.max(max, count)
        return max
    }

    if (sum == 50) {
        count++
        sum += comb[right++]
        sum -= comb[left++]
    } else if (sum > 50) {
        sum -= comb[left++]
    } else {
        sum += comb[right++]
    }

    return twoPointer(left, right, sum, count)
} // End of twoPointer()

private fun input() {
    N = br.readLine().toInt()

    val st = StringTokenizer(br.readLine())
    arr = IntArray(N) { idx ->
        st.nextToken().toInt()
    }
} // End of input()