★Divide & Conquer Advanced I - 5 Solved★

★ 18291 비요뜨의 징검다리 건너기 ★

import sys
input=sys.stdin.readline

def power_divide_conquer(a,b,c):
    if b==1:
        return a%c
    
    halved = power_divide_conquer(a,b//2,c)

    if b%2==0:
        return ((halved%c) * (halved%c)) %c
    else:
        return ((halved%c) * (halved%c) * (a%c))%c

BIG = 1000000007

for _ in range(int(input())):
    N=int(input())
    if N==1:
        print(1)
    elif N==2:
        print(1)
    else:
        print(power_divide_conquer(2,N-2,BIG)%BIG)

 

📣 징검다리의 개수를 X라고 할 때 1번 다리부터 X번 다리까지 건너는 경우의 수를 구하는 문제. 

: P(n)을 1번에서 n번 다리까지 건넌 경우의 수라고 한다면, 1번에서 X번까지 갈 수 있는 모든 경우의 수는 1번에서 1번까지 건넌 모든 경우(1번에서 X번까지 한 번에) + 1번에서 2번까지 건넌 모든 경우(2번에서 X번까지 한 번에) + .... 1번에서 (X-1)번까지 건넌 모든 경우(X-1번에서 X번까지 한 번에)이며, P(n)을 이용해서 나타낸다면 P(X) = P(1) + P(2) + P(3) + ... P(X-1)이다.

 

📣 P(1) = 1, P(2) = 1 이므로 P(3) = P(2) + P(1) =1 + 1 = 2 / P(4) = P(3) + P(2) + P(1) = 2 + 1 + 1 = 4 / P(5) = 4 + 2 + 1 + 1 = 8  ....  / P(X) = 2 ^ (X-2)임을 규칙으로 알 수 있다. 따라서 2^(X-2)를 1,000, 0007로 나눈 나머지를 구한 결과가 정답

 

📣 A^B을 C로 나눈 나머지를 구하는 과정은, B가 매우 클 경우(위 문제 한정 B<=10^9) 분할정복을 이용한 거듭제곱으로 구한다(별도 포스팅 참조)

---

★ 5904 Moo 게임 ★

def dc(numbers,order,center_num):
    half_num = (numbers-center_num)//2
    if order<=half_num:
        dc(half_num,order,center_num-1)
    elif (half_num+1)<=order<=(half_num+center_num):
        if order == (half_num+1):
            print('m')
            return
        else:
            print('o')
            return
    else:
        dc(half_num,order-(half_num+center_num),center_num-1)

N=int(input())

#k
k=3
bf=0
cum=3
while cum<N:
    bf=cum
    cum*=2
    cum+=(k+1)
    k+=1

if (N-bf)<=k:
    if (N-bf) == 1:
        print('m')
    else:
        print('o')
else:
    numbers_in_a_cycle = cum-bf-k
    order = N-bf-k
    center_num = k-1
    dc(numbers_in_a_cycle,order,center_num)

 

📣 m o ..... o를 한 개의 문자열로 보고 문자열의 길이를 왼쪽부터 나열한다면 아래와 같다.

 

3 4 3 5 3 4 3 6 3 4 3 5 3 4 3 7 3 4 3 5 3 4 3 6 3 4 3 5 3 4 3 8 ...

 

이를 그룹화하자면

① 입력받은 N이 어느 그룹에 속하는 지 먼저 판단. 위 그림과 같이 각 그룹의 그룹 내의 최댓값 k가 있다. 즉, k를 구한다. k를 구하고 나면 k가 속한 그룹을 분석해 보면 아래와 같다 (ex k = 7)

② group 내에 2가지 케이스로 나눌 수 있는데,

(1) N번째 해당되는 문자가 group 내에 1번째부터 k번째 안에 들어가 있는 경우

(2) N번째 해당되는 문자가 group 내에 (k+1)번째부터 group 끝까지 들어가 있는 경우

 

③ bf와 cum을 먼저 구한다. bf는 앞 group까지의 모든 숫자 개수, cum은 현재 속해 있는 group 끝까지의 모든 숫자 개수.

(1) - 1: (N-bf) == 1일 경우, group 내의 맨 첫번째 이기에 바로 'm' 출력

(1) - 2:  위 (1)-1이 아닌 경우 바로 'o' 출력

 

④ 위 (1)이 아닌 경우, 분할정복 기법으로 m인지 o인지 알아내면 된다. group내에 앞의 k개의 글자를 제외한 나머지는 위 그림과 같이 center_num(k-1)을 기점으로 좌우가 동일(분할정복을 사용하기에 알맞다)하다. 따라서 left + center_num + right을 cycle이라 정의하고 아래와 같이 3개를 구함

(1) numbers_in_a_cycle: cycle 내의 개수

(2) order: N번째 글자가 cycle 내에서 몇 번째에 해당되는 지

(3) center_num: cycle 내의 중심이 되는, cycle내의 가장 큰 최댓값

 

⑤ 그러면 ④에서 구한 (1), (2), (3)을 이용해 분할정복 진행

(1) order가 center_num보다 왼쪽 left part에 위치해 있다면, (즉 위 그림 기준 3 4 3 left part에 위치해 있다면), left part를 재귀적으로 분할정복 진행

(2) order가 center_num에 위치해 있다면 (즉 위 그림 기준 5에 위치해 있다면), order가 half_num + 1일 경우 'm' 출력, 그렇지 않으면 'o' 출력

(3) order가 center_num보다 오른쪽 right part에 위치해 있다면 right part를 재귀적으로 분할정복 진행

 

: 즉 위 그림과 같이 center를 기준으로 좌우가 동일하므로 위치해 있는 부분에 따라 좌 또는 우 각각에 분할 정복 진행. 계속 divide 해나가다가 center_num part에 속할 때 m 또는 o (center_num part 맨 앞이면 m, 그렇지 않으면 o) 출력

---

★ 2447 별 찍기 - 10 ★

N=int(input())
ans=[['?']*N for _ in range(N)]

def star(N,x,y):
    global ans
    if N <= 1:
        return
    #(1) upper 
    for i in range(N//3):
        for j in range(N):
            ans[x+i][y+j] = '*'

    #(2) middle
    for i in range(N//3):
        for j in range(N):
            if 0<=j<N//3 or (N//3)*2<=j<N:
                ans[x+(N//3)+i][y+j] = '*'
            else:
                ans[x+(N//3)+i][y+j] = ' '

    #(3) below
    for i in range(N//3):
        for j in range(N):
            ans[x+(N//3)*2+i][y+j] = '*'

    star(N//3,x,y)
    star(N//3,x,y+N//3)
    star(N//3,x,y+(N//3)*2)
    star(N//3,x+N//3,y)
    star(N//3,x+N//3,y+(N//3)*2)
    star(N//3,x+(N//3)*2,y)
    star(N//3,x+(N//3)*2,y+N//3)
    star(N//3,x+(N//3)*2,y+(N//3)*2)

star(N,0,0)

for l in ans:
    print(*l,sep='')

 

📣 큰 틀의 규칙을 찾고, 부분부분 나누어가면서(divide) 무늬를 규칙적으로 그리는(conquer) 방식으로 진행

 

① 먼저 모두 ?로 만들고 난 다음, size N x N 정사각형에서 위 / 중간 / 아래 각각 *나 빈 칸으로 바꾸기(페인트 칠하기)

② 그 다음 두번째 줄 중간 파트를 제외하고, 남은 8개 파트에서 동일하게 진행(재귀적) (위 start(~) 8개 코드)

: 위 그림과 같이 전체 사각형에서 1, 2, 3 위쪽은 모두 *, 중간은 4와 6 *, 그리고 5만 빈칸. 7, 8, 9는 모두 *. 이후 파트 5만 제외하고 남은 8개의 파트(분할 결과) 모두 각각 재귀로 동일하게 정복 진행. 결과 size N이 1이 되면 종료.

 

📣 size N에 맞게 x,y 각각 index만 정확한 값으로 넣으면 끝

---

★ 15717 떡파이어 ★

def get_power_by_divisor(a,b,c):
    if b == 1:
        return a%c
    else:
        x = get_power_by_divisor(a,b//2,c)
        if b%2 == 0:
            return ((x%c) * (x%c))%c
        else:
            return ((x%c) * (x%c) * (a%c))%c 

N = int(input())
if N == 0:
    print(1)
elif N == 1:
    print(1)
else:
    print(get_power_by_divisor(2,N-1,10**9+7))

 

📣 <18291 비요뜨의 징검다리 건너기> 문제와 유사

 

📣 N에서의 경우의 수를 P(N)이라 하면 P(1) + P(2) + ... + P(N-1) + 1이다. 즉, 1을 만드는 경우의 수 각각에서 N-1을 더한다면 N이 된다. 2부터 N-1까지도 마찬가지. 이 때, N 자체의 경우의 수 1가지 더 더해준다. P(1) = 1, P(2) = 2를 베이스로 P(N) = 2^(N-1)로 나타낼 수 있으며, 이 때 지수 N이 최대 10^12로 매우 크므로 분할정복을 이용한 거듭제곱을 활용해 답을 구하면 된다.

---

★ 29578 Сумма степеней ★

def pdq(a,b,c):
    if b <= 1:
        return a%c
    halved = pdq(a,b//2,c)
    if b%2==1:
        return ((halved%c) * (halved%c) * (a%c))%c
    else:
        return ((halved%c) * (halved%c) )%c

n = int(input())

num = 1
cnt = 0
while cnt < n:
    two = pdq(2,num,num)
    four = (two*two)%num
    three = pdq(3,num,num)
    six = (three*two)%num
    five = pdq(5,num,num)
    if (1+two+three+four+five+six)%num == 0:
        cnt+=1
        ans=num
    num+=1
print(ans)

 

📣 1 + 2^k + ... 6^k이 k로 나누어지는 지 알아보는 문제. n번째 나누어지는 수인 k를 출력. 2^k (mod k) ~ 6^k(mod k) 각각 구하는 방법도 있으나, 4^k(mod k)는 2^k(mod k) 구한 결과를 제곱, 6^k(mod k)는 (2^k(mod k) * 3^k(mod k)) % k로 조금 더 빨리 구할 수 있다. 실제로는 밑이 2, 3, 5인 세 가지 경우만 구해도 ok(구할 때 k 지수가 매우 커질 수 있으므로, (실제 n이 최대 65일 때 지수 k는 44247이다) 분할 정복을 이용한 거듭제곱 알고리즘 사용)

---