시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 21 | 3 | 3 | 21.429% |
태와 도토리는 크기가 N×M인 직사각형 초콜릿을 하나 가지고 있다. 초콜릿은 1×1크기의 칸으로 나누어져 있으며, 각각의 칸은 T, D, U중 하나의 글자가 적혀져 있다. 초콜릿을 먹기 위해 다음과 같은 방법으로 두 조각으로 나누려고 한다.
XX XX
초콜릿의 크기와 칸에 쓰여 있는 문자가 주어졌을 때, 초콜릿을 두 조각으로 나누는 방법의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 N, M, K가 주어진다. (1 ≤ N, M ≤ 8, 0 ≤ K ≤ N×M) 둘째 줄부터 N개의 줄에는 초콜릿의 칸에 적혀있는 문자가 주어진다. 각각의 줄은 총 M개의 문자로 이루어져 있으며, 각 문자는 T, D, U중 하나이다.
첫째 줄에 초콜릿을 두 조각으로 나누는 방법의 수를 출력한다.
2 2 4 UU UU
12
T를 태가 가져간 조각, D를 도토리가 가져간 조각이라고 했을 때, 총 24 = 16가지 방법 중 아래와 같은 4가지 방법은 불가능하다.
TT TT DD DD DT TD TD DT