두번째는 나올 수 있는 조합을 o,x로 표현하여 규칙을 찾아보았다. 그런데 문제 특성상 하나의 조각이 나누어지기 전에는 절대 반조각이 나올 수 없다는 점을 고민하다가 반조각의 경우 한조각이 나온 횟수보다 많으면 안되겠구나 라고 생각 -> 바로 그래프로 표현해봤는데 그림에서 아래와같이 중복조합 길찾기와 같은 문제라는걸 깨달았다.(사실 고딩때였다면 바로 풀었을지도..?... 난 퇴화했다 어쩐지 골드5..)
이후부터는 그냥 dp테이블을 구성하고 구현하면 끝!
최종코드
import sys; input = sys.stdin.readline
dp = [[1]*31 for _ in range(31)]
for i in range(1, 31):
for j in range(i, 31):
if j == i:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i][j-1] + dp[i-1][j]
while True:
n = int(input())
if n == 0:
break
print(dp[n][n])
-> dp문제이기 때문에 점화식 안됐으면 빨리 다른방식 생각해볼걸 그랬다. dp문제는 정해져있는 여러 풀이법들을 안되면 빠르게 바꿔서 적용해보면서 시간을 낭비하지 말아야 겠다.
생각보다 dp가 점화식으로 어이없게 빨리풀리는 경우가 있어서..점화식을 일단 의심해보는 습관이 있는것 같다 ㅋㅋㅋㅋ
