[백준/Kotlin] 알약(4811)

문제

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

 

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.

첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.

다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.

종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

 

[ 입력 ]

입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

 

[ 출력 ]

각 테스트 케이스에 대해서 가능한 문자열의 개수를 출력한다.

 

---

풀이

- 알약이 최대 30개까지 입력으로 들어오기 때문에 30개까지의 값을 모두 구해두기

- dp를 이용해서 반조각, 한조각 알약 개수에 따라 계산

- 경우의 수가 int 범위를 넘어갈 수 있기 때문에 Double 자료형 사용

 

// 백준 - 알약(4811)
import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
  var br = BufferedReader(InputStreamReader(System.`in`))

  // 한조각 알약 i개, 반조각 알약 j개가 남았을 때
  var dp: Array<Array<Double>> = Array(31, {Array(31, {0.0})})

  // 반조각짜리만 남아있는 경우 = 반알짜리만 뽑게 되므로 경우의 수 1개
  for(i: Int in 1..30) {
    dp[0][i] = 1.0
  }

  for(i: Int in 1..30) {
    for(j: Int in 0..29) {
      // 아직 반조각 알약이 없는 경우
      if(j == 0) dp[i][j] = dp[i-1][j+1]
      // 반조각 알약이 있는 경우 = 한조각짜리를 먹은 경우 + 반조각짜리를 먹은 경우
      else dp[i][j] = dp[i-1][j+1] + dp[i][j-1]
    }
  }

  var answer = StringBuilder()
  var medicine = br.readLine().toInt()

  while(medicine != 0) {
    answer.append(String.format("%.0f", dp[medicine][0])).append("\n")

    medicine = br.readLine().toInt()
  }

  print(answer)
}