[UCPC][2019][예선] C번 풀이 미완성
문제
풀이
11을 22로 바꾸거나 22를 11로 바꾸는 연산(1x1 두 개를 1x2로 합치거나, 1x2를 두 개의 1x1로 나누는 연산)을 기본 연산이라고 하겠습니다.
두 배열에 저장하기
문제에서 두 번째 줄의 입력(a1, a2, …)을 입력 받으면서 1을 입력받으면 한 칸에 1을 적고, 2를 입력 받으면 연속한 두 칸에 2를 넣었습니다.
1 1 1을 입력 받으면 1 1 1
1 2 를 입력 받으면 1 2 2
1 2 2를 입력 받으면 1 2 2 2 2
와 같이 배열 a에 저장한 것입니다. 네 번째 줄도 같은 방식대로 배열 b에 저장했습니다.
그리고 필요한 연산을 두 가지 종류로 나눠서 각 연산의 갯수를 구했습니다.
두 개의 연산을 정의하고 각 연산의 필요 횟수 구하기
x 연산 : 배열에 저장한 수들을 왼쪽부터 읽으면서(0 <= i < L), a[i]를 b[i]와 일치시키기 위한 연산을 바로 진행할 수 있는 경우. (a[i]를 b[i]를 일치시키기 위해서 기본연산을 1번 실행하는 경우)
변환 전 저장된 배열 : 1 1
일치시킬 배열의 상태 : 2 2
또는
변환 전 저장된 배열 : 2 2
일치시킬 배열의 상태 : 1 1
y 연산 : 배열에 저장한 수들을 왼쪽부터 읽으면서(0 <= i < L), a[i]를 b[i]와 일치시키기 위한 연산을 바로 진행할 수 없고, a[i+1]칸을 바꾼 뒤에 a[i]를 b[i]와 일치시킬 수 있는 경우 (a[i]를 b[i]를 일치시키기 위해서 기본연산을 2번 실행하는 경우)
변환 전 저장된 배열 : 1 2 2
일치시킬 배열의 상태 : 2 2 1
또는
변환 전 저장된 배열 : 2 2 1
일치시킬 배열의 상태 : 1 2 2
결론적으로,
변환 전 저장된 배열 : 1 2 2 1 1 1 일치시킬 배열의 상태 : 2 2 1 2 2 1
의 경우 x 연산과 y연산은 각 1번씩 필요합니다.
그리고
변환 전 저장된 배열 : 1 2 2 2 2 2 2 2 2 1
일치시킬 배열의 상태 : 2 2 2 2 2 2 2 2 2 2
의 경우 x 연산과 y연산은 각 1번과 4번이 필요합니다.
x와 y 연산을 사용하여 정답 계산하기
정답 : 첫 번째 줄에 필요한 연산의 최소 횟수와 그 때 방법의 가짓수를 공백을 사이에 두고 출력한다. 방법이 많아질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.
(x+2y) 와 (x+2y)!/(pow(2,y))를 공백을 사이에 두고 출력하면 됩니다. 왜냐하면 x와 y 연산의 정의에 따라서 x 연산은 기본연산을 1번, y 연산은 2번 필요로하는데 y연산의 두 기본연산은 순서가 정해져있기 때문입니다. 따라서 전체 (x+2*y)연산의 factorial을 구하고, 2의 y승으로 나누어서 출력합니다.