[백준/Kotlin] 비즈 공예(1301)

문제

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

다솜이는 자신의 목걸이를 구슬을 이용해서 만들려고 한다. 다솜이는 구슬을 N종류 가지고 있다. 서로 다른 종류의 구슬은 색이 다르다. 다솜이는 구슬을 실에 껴서 목걸이를 만들려고 한다. 무작정 껴도 상관없겠지만, 워낙 미적감각이 뛰어난 다솜이는 임의의 연속된 3개의 구슬의 색을 모두 다르게 하려고 한다.

예를 들어, 다솜이가 1번 구슬을 2개, 2번 구슬을 1개, 3번 구슬을 1개 가지고 있다고 하자. 1번 구슬이 초록, 2번 구슬이 파랑, 3번 구슬이 빨강이라고 하면, 연속된 3개의 구슬이 같은 색이면 안되기 때문에, 초록구슬을 반드시 목걸이의 끝에 있어야 한다. 따라서 다솜이가 목걸이를 만들 수 있는 방법의 경우의 수는 초록-빨강-파랑-초록 또는 초록-파랑-빨강-초록 총 2가지이다.

반드시 가지고 있는 모든 구슬을 이용해야 하며, 목걸이는 원형이 아니라 직선이다. 다시말하면, 처음 구슬과 마지막 구슬은 이어져있는 것이 아니다.

다솜이가 목걸이를 만들 수 있는 방법의 경우의 수를 구하는 프로그램을 작성하시오.

 

[ 입력 ]

첫째 줄에 다솜이가 가지고 있는 구슬의 종류 N이 주어진다. N은 3보다 크거나 같고, 5보다 작거나 같다. 둘째 줄부터 N개의 줄에 각각의 구슬이 총 몇 개 있는 지주어진다. 첫째 줄에는 1번 구슬, 둘째 줄에는 2번 구슬, 이런 형식이다. 각각의 구슬은 10개보다 작거나 같은 자연수이다. 그리고, 구슬의 총 개수의 합은 35를 넘지 않는다.

 

[ 출력 ]

첫째 줄에 다솜이가 목걸이를 만들 수 있는 방법의 경우의 수를 출력한다.

 

풀이

• DP를 이용
• dp[1번][2번][3번][4번][5번][전][전전]
• 연속된 3개의 구슬 색이 다른지 판별하기 위해 전, 전전 구슬의 색깔을 알아야 한다

// 백준 - 비즈 공예(1301)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

// 7차원
// 구슬 1~5번의 남은 개수 + 이전 구슬, 전전 구슬
// [1번][2번][3번][4번][5번][전][전전]
var dp = Array(11, { Array(11, { Array(11, { Array(11, { Array(11, { Array(11, { LongArray(11, {-1}) }) }) }) }) }) })

fun dpBeads(beads: Array<Int>, pre: Int, prepre: Int): Long {
  // 구슬을 다 썼을 경우
  if(beads[1] == 0 && beads[2] == 0 && beads[3] == 0 && beads[4] == 0 && beads[5] == 0) return 1

  var cur: Long = dp[beads[1]][beads[2]][beads[3]][beads[4]][beads[5]][pre][prepre]
  // 이미 값이 있을 경우
  if(cur != -1L) return cur

  cur = 0L
  for(i: Int in 1..5) {
    // 연속된 3개의 구슬의 색이 모두 다를 때
    if(pre != i && prepre != i && beads[i] > 0) {
      beads[i]--
      cur += dpBeads(beads, i, pre)
      beads[i]++
    }
  }
  dp[beads[1]][beads[2]][beads[3]][beads[4]][beads[5]][pre][prepre] = cur
  return cur
}

fun main() {
  val br = BufferedReader(InputStreamReader(System.`in`))
  var N = br.readLine().toInt()

  var beads = Array<Int>(6, {0})

  for(i: Int in 1..N) {
    beads[i] = br.readLine().toInt()
  }

  var answer: Long = dpBeads(beads, 0, 0)
  print(answer)
}

 

 

< 실패한 코드 >

• 구슬이 3 종류일 때를 기준으로 생각해서 틀렸다

// 백준 - 비즈 공예(1301) - 실패
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import kotlin.math.max
import kotlin.math.min

fun main() {
  val br = BufferedReader(InputStreamReader(System.`in`))
  var N = br.readLine().toInt()

  var beads = Array(11, {0})
  var max = 0
  var min = 35

  for(i: Int in 0..N-1) {
    var input = br.readLine().toInt()

    max = max(max, input)
    min = min(min, input)

    beads[input]++
  }

  // 구슬을 다 쓸 수 없는 경우 = 목걸이 조합 불가
  if(max - min > 1) {
    print(0)
    return
  }

  // 구슬의 개수가 모두 동일한 경우 = N!가지 경우의 수
  if(max == min) {
    var answer = 1
    for(i: Int in 2..N) {
      answer *= i
    }
    print(answer)
  }

  // 구슬의 개수가 다른 경우 => 구슬이 3종류일 때, 그 이상일 때를 분리
  // = N!가지에서 겹치는 구슬 가지수!
  // 예) 1,2번 구슬은 1개씩, 4,5,6번 구슬은 2개씩 있을 경우
  // 1개씩인 구슬 2가지, 2개씩인 구슬 3가지
  // 2! * 3!
  if(max != min) {
    var answer = 1
    for(i: Int in 1..10) {
      if(beads[i] > 1) {
        for(j: Int in 2..beads[i]) {
          answer *= j
        }
      }
    }
    print(answer)
  }
}