1328번 - 고층 빌딩
점화식이 이상한데 설명하자면 이렇습니다
예시) N = 5, L = 2, R = 2인 경우의 답을 구해보자.
5의 가능한 위치는 L = 2 부터 N-R+1 = 3까지
1. 5의 위치가 2일때
편의상 배치를 ㅁ5ㅁㅁㅁ으로 나타내자.
ㅁ5ㅁㅁㅁ 왼쪽 ㅁ에 들어갈 숫자를 정하는 경우의 수는 4C1, 그리고 왼쪽의 ㅁ5를 완성하는데 가능한 경우는
N=2 일 때 L = 2, R = 1인 경우와 같다. 그리고 오른쪽 5ㅁㅁㅁ을 완성하는데 가능한 경우는 N=4일 때, L=1, R = 2인 경우와 같다.
따라서 4 * 1 * 2 = 8
2. 5의 위치가 3일때
ㅁㅁ5ㅁㅁ 5의 왼쪽인 ㅁㅁ에 들어갈 숫자를 정하는 경우의 수는 4C2, 그리고 왼쪽의 ㅁㅁ5를 완성하는데 가능한 경우는
N=3 일 때, L = 2, R = 1인 경우와 같고, 5ㅁㅁ을 완성하는 경우의 수는 N=3일때 L=1, R= 2인 경우와 같다.
따라서 6*1*1 = 6
3. 5의 위치가 4일때
1번과 대칭이므로 생략하겠습니다. 본 소스에선 계산을 합니다.
아무래도 곱셈연산의 나머지 연산에서 뭔가 문제가 생긴 듯 한데
제가 데이터 타입을 unsigned long long 으로 선언해서 1000000007 * 1000000007해도 unsigned long long 최대범위보다 작으므로 두 수끼리 곱할때마다 나머지 연산 해주면 아무 문제 없이 작동할 것 같았거든요.
혹시 어떤 문제가 있는지 가르쳐주시면 감사하겠습니다.
괄호 순서가 틀렸었네요.
100 2 2
598881956
100 50 51769496025
100 51 50769496025
100 52 500
100 1 2990953332
100 2 1990953332
댓글을 작성하려면 로그인해야 합니다.
kinssang 6년 전
점화식이 이상한데 설명하자면 이렇습니다
예시) N = 5, L = 2, R = 2인 경우의 답을 구해보자.
5의 가능한 위치는 L = 2 부터 N-R+1 = 3까지
1. 5의 위치가 2일때
편의상 배치를 ㅁ5ㅁㅁㅁ으로 나타내자.
ㅁ5ㅁㅁㅁ 왼쪽 ㅁ에 들어갈 숫자를 정하는 경우의 수는 4C1, 그리고 왼쪽의 ㅁ5를 완성하는데 가능한 경우는
N=2 일 때 L = 2, R = 1인 경우와 같다. 그리고 오른쪽 5ㅁㅁㅁ을 완성하는데 가능한 경우는 N=4일 때, L=1, R = 2인 경우와 같다.
따라서 4 * 1 * 2 = 8
2. 5의 위치가 3일때
ㅁㅁ5ㅁㅁ 5의 왼쪽인 ㅁㅁ에 들어갈 숫자를 정하는 경우의 수는 4C2, 그리고 왼쪽의 ㅁㅁ5를 완성하는데 가능한 경우는
N=3 일 때, L = 2, R = 1인 경우와 같고, 5ㅁㅁ을 완성하는 경우의 수는 N=3일때 L=1, R= 2인 경우와 같다.
따라서 6*1*1 = 6
3. 5의 위치가 4일때
1번과 대칭이므로 생략하겠습니다. 본 소스에선 계산을 합니다.
아무래도 곱셈연산의 나머지 연산에서 뭔가 문제가 생긴 듯 한데
제가 데이터 타입을 unsigned long long 으로 선언해서 1000000007 * 1000000007해도 unsigned long long 최대범위보다 작으므로 두 수끼리 곱할때마다 나머지 연산 해주면 아무 문제 없이 작동할 것 같았거든요.
혹시 어떤 문제가 있는지 가르쳐주시면 감사하겠습니다.