[Week 6] MORSE self review - Scaachan

[Queue-ri]

MORSE self review

• 파일명: MORSE/Scaachan.cpp
• 수행시간: 0ms

1. 문제 해결 과정

nCr을 이용하는 것 같긴 한데, 어느 지점에서 재귀해야 할지 생각이 안나서 재귀 함수 설계는 책을 참고했습니다.

2. 아이디어

nCr 응용 DP

3. 코드 설명

https://github.com/Scaachan/Advanced-Algorithm-Study/blob/e41c28d4a443f85310735353af5f6e5a17425e42/MNO/MORSE/Scaachan.cpp#L11-L16

nCr 을 계산하는 함수입니다.

K 값의 범위가 정해져 있기 때문에, MAX와 값을 비교하여 최대 1,000,000,001 까지만 고려합니다.

rep(r, 0, 101)
	rep(n, r, 201)
		nCr(n, r);

main에선 이런 식으로 nCr (Dom(n) = [0, 101), Dom(r) = [n, 201)) 을 미리 다 계산해서 캐시에 저장해둡니다.

문제 조건 상 n < r 의 경우는 쓰일 일이 없을 것이라 생각하여 계산하지 않았습니다.

https://github.com/Scaachan/Advanced-Algorithm-Study/blob/e41c28d4a443f85310735353af5f6e5a17425e42/MNO/MORSE/Scaachan.cpp#L18-L23
n은 -의 개수이고, m은 o의 개수를 뜻합니다.

맨 앞에 문자 한개가 고정되어있다고 가정한 뒤 식을 세웁니다.

문자는 항상 -가 o보다 먼저 놓인 상태로 시작하니,

K의 값이 n+m-1 C n-1 보다 같거나 작을 때 그 문자는 -가 되고, 반대로 더 크다면 o가 됩니다.

ex.

--oo 에서 맨 앞 -는 나머지 -oo 조합의 모든 경우의 수(3C2 : {-oo, o-o, oo-})가 끝날 때까지 그 자리에 있습니다.

하지만 그 다음 케이스부턴 자리가 바뀌어서, o--o 와 같이 o로 시작하게 됩니다.