BOJ :: 알약 (no.4811)

숑숑·2021년 2월 24일
0

알고리즘

목록 보기
78/122
post-thumbnail

문제

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

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

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

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

입력

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

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

출력

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


🤔 생각

  • 문제 상황이 조금 복잡하기도 하고 그래서 뭘 구해야 하는지 한번에 들어오지 않았다...
  • 정리하면서 문제 상황을 단순화해보자
  • 풀면서 주석으로 쓴 필기를 그대로 복붙해보겠다

문제 상황

길이가 2n개니 알약 한통을 다썼다는 소리.
알약을 다 쪼개려면? -> 결국 n개 모두 쪼개긴 해야함
즉, w가 n개. h 또한 무조건 n개 여야 함

문제 정리

w가 n개고, h가 n개인 문자열의 경우의 수
w: 한 조각
h: 반 조각

배열

dp[i][j] : h가 i개고, w가 j개일 때 경우의 수

dp[h][w]

점화식

dp[h][w] = dp[h-1][w] + dp[h][w-1]

주의 사항

한개만 있는 경우는 모두 1
반개가 더 많은 경우는 모두 0 (불가능한 경우임)


📌 내 풀이

import sys
input = sys.stdin.readline

nums = []
while True:
    N = int(input())
    if N == 0: break
    nums.append(N)

MAX = max(nums) + 1
dp = [[0]*MAX for _ in range(MAX)]
dp[0] = [1]*MAX

for h in range(1,MAX):
    for w in range(h,MAX):
        dp[h][w] = dp[h-1][w] + dp[h][w-1]

for n in nums:
    print(dp[n][n])

✔ 회고

  • 한개만 있는 경우까진 괜찮은데, 반개가 더 많은 경우가 불가능하다는걸 떠올리는게 오래 걸렸다.
  • 항상 큰 틀은 정답과 가깝게 접근하지만, 인덱스 같은 세세한 접근이 부족한 것 같다...
profile
툴 만들기 좋아하는 삽질 전문(...) 주니어 백엔드 개발자입니다.

0개의 댓글