4811 알약

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

4811번: 알약

---

접근

분명히 이전에 계산한 값을 활용하는게 DP일텐데... 점화식이 어렴풋이 보이는 것 같기도 하고...

 

문제 이해를 잘 못해 2N일이 지나면 조합의 개수가 2N개인줄 알고 예시를 만들어봐도 안되길래 뭐가 문젠가 싶어 문제를 제대로 읽어보았다.

 

1. 첫째 날에 알약통에서 온전한 알약 한 조각을 반으로 나눠 하나를 먹고 나머지는 다시 알약통에 넣는다.

2. 둘째 날에 알약통에서 알약 하나를 꺼낸다.

2-1. 온전한 알약일 경우 첫째 날에  했던 행동을 그대로, 알약 한 조각을 반으로 나눠 하나를 먹고 나머지는 다시 알약통에 넣는다.

2-2. 반으로 쪼개진 알약일 경우 그냥 먹는다.

 

간단히 예시를 들어보면 아래처럼 나타난다.

# N = 2일때

# day 1
(1,1) 		# W	온전한 알약 1개를 반으로 나누고 1개를 먹음

# day 2
(0,2)		# WW	온전한 알약 1개를 반으로 나누고 1개를 먹음
(1,0)		# WH	쪼개진 알약 1개를 먹음

# day 3
(0,1)		# WWH	쪼개진 알약 1개를 먹음
(0,1)		# WHW	온전한 알약 1개를 반으로 나누고 1개를 먹음

# day 4
(0,0)		# WWHH	쪼개진 알약 1개를 먹음
(0,0)		# WHWH	쪼개진 알약 1개를 먹음

 

# N = 3일때

# day 1
(2,1)		# W		온전한 알약을 반으로 나누고 하나를 먹음

# day 2
(1,2)		# WW		온전한 알약을 반으로 나누고 하나를 먹음
(2,0)		# WH		쪼개진 알약을 먹음

# day 3
(0,3)		# WWW		온전한 알약을 반으로 나누고 하나를 먹음
(1,1)		# WWH		쪼개진 알약을 먹음	<-- N=2에서 이미 구한 값이다!
(1,1)		# WHW		온전한 알약을 반으로 나누고 하나를 먹음  <-- N=2에서 이미 구한 값이다!

# day 4
(0,2)		# WWWH		쪼개진 알약을 먹음
(0,2)		# WWHW		온전한 알약을 반으로 나누고 하나를 먹음
(1,0)		# WWHH		쪼개진 알약을 먹음
(0,2)		# WHWW		온전한 알약을 반으로 나누고 하나를 먹음
(1,0)		# WHWH		쪼개진 알약을 먹음

# day 5
(0,1)		# WWWHH		쪼개진 알약을 먹음
(0,1)		# WWHWH		쪼개진 알약을 먹음
(0,1)		# WWHHW		온전한 알약을 반으로 나누고 하나를 먹음
(0,1)		# WHWWH		쪼개진 알약을 먹음
(0,1)		# WHWHW		온전한 알약을 반으로 나누고 하나를 먹음

# day 6
(0,0)		# WWWHHH	쪼개진 알약을 먹음
(0,0)		# WWHWHH	쪼개진 알약을 먹음
(0,0)		# WWHHWH	쪼개진 알약을 먹음
(0,0)		# WHWWHH	쪼개진 알약을 먹음
(0,0)		# WHWHWH	쪼개진 알약을 먹음

예시를 쓰느라 매우 길어졌는데 위의 예시를 잘 살펴보면,  N=2에서 보았던 온전한 알약의 개수와 쪼개진 알약의 개수가 N=3에서도 또 등장한다.

 

여기서 어떤 온전한 알약의 개수와 쪼개진 알약의 개수에 대해 구했던 값을 재활용 하는 것임을 알았다.

 

이걸 저장하기 위해서는 2차원 배열이 딱이었다. 변수 2개로 이루어지는 저장공간이니까...

그러니까 온전한 알약의 개수(i)와 쪼개진 알약의 개수(j)에 대해 가능한 조합은 dp[i][j]라고 할 수 있다.

 

이제 dp[i][j]를 구하기 위해 아까 정리했던 순서도를 활용해 아래처럼 정리했다.

 

만약 i가 0보다 크다면 온전한 알약 하나를 쪼개는 방법을 사용할 수 있으므로,

→ 결과값에 dp[ i - 1 ][ j + 1 ]을 더한다.

 

만약 j가 0보다 크다면 쪼개진 알약 하나를 먹는 방법을 사용할 수 있으므로,

→ 결과값에 dp[ i ][ j - 1 ]을 더한다.

 

그리고, (0, 4)처럼 쪼개진 알약만 있는 경우는 어떻게 하든지 조합이 HHHH밖에 나오지 않으니, dp[ i ][ j - 1 ]값을 더하는 과정에서 결과값이 1이 되도록 dp[ 0 ][ 0 ]을 1로 정한다.

 

30을 입력했을때 억단위를 넘어가는 답이 나오기 때문에 자료형을 long long을 설정했다.

미흡했던 점

문제를 속독하지말고 차근차근히 읽어보면서 문제가 요구하는게 어떤 것인지 생각하는 시간을 가져야겠다.

 

솔직히 입력예시만 보고 '아 무슨 말인지 알겠다' 하는 경우가 많았다. 그런대로 이해가 되어 해결하는데 어려움이 없었기 때문에 천천히 읽는 습관이 들지 않았다. 천천히 읽자.

---

#include <iostream>
long long dp[31][31]{0};
long long f(int i, int j) {
  if (!dp[i][j]) {
    if (j > 0) {
      dp[i][j] += f(i, j - 1);
    }
    if (i > 0) {
      dp[i][j] += f(i - 1, j + 1);
    }
  }
  return dp[i][j];
}
int main() {
  int N;
  dp[0][0] = 1;
  while (1) {
    scanf("%d", &N);
    if (N == 0) {
      break;
    }
    printf("%lld\n", f(N - 1, 1));
  }
}