PS/백준
[BOJ] 2407 조합 (C/C++)
uyt8989
2022. 3. 19. 20:57
2407번: 조합
n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)
www.acmicpc.net
문제
nCm을 출력한다.
입력
n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)
출력
nCm을 출력한다.
문제가 참 심플하다. 널리 알려져 있는 다음과 같은 점화식을 사용해서 쉽게 풀 수 있을 줄 알았다. 점화식이 이미 들통한 DP 문제만큼 쉬운 문제는 없다. 메모이제이션 + DP를 사용하면 간단하게 풀린다. 하지만 숫자가 너무 커서 이걸 문자열로 계산해야 하는 문제였다.
$$ \binom{n-1}{m-1} + \binom {n-1}{m} = \binom{n}{m} $$
문자열로 계산을 하다보니 그냥 출력하면 거꾸로 나온다. 그래서 출력을 뒤집어야 한다.
후기)
문제가 그리 어렵지는 않았다. 하지만 수식을 문자열로 계산하는걸 진짜 오랜만에 해본 것 같다. 아마 1학년 때 기초 코딩 과목을 들으면서 였겠지...? 오랜만이라 감회가 새로웠다.