[알고리즘 연습] 2021년도 10월 셋째주 학습 (D번 문제 풀이)

AtCoder Beginner Contest 222 (D번 문제): DP
Codeforces Round #748 (Div.3) (D1번 문제): 유클리드 호제법

 

대회를 진행하면 항상 A, B, C번을 풀고 D 번에서 막히기 때문에 시간을 내서 D번 정식 풀이를 학습해보았다.

 

1. AtCoder Beginner Contest 222 (D번 문제)

문제

https://atcoder.jp/contests/abc222/tasks/abc222_d

 

풀이

조건이 복잡하기 때문에 모든 경우의 수를 단순히 곱해서 구할 수 없다.

재귀함수를 통해 일일히 가능한 경우를 세면 엄청나게 많은 가짓수가 있기 때문에 시간 초과가 난다.

이미 구한 값을 이용하여 다음 값을 계산하는 DP 접근 방식이 필요하다.

 

직접 예시를 만들어보면 가능한 가짓수는 현재 값보다 작거나 같은 것들의 누적합임을 알 수 있다.

코드

https://atcoder.jp/contests/abc222/submissions/26608100

import numpy as np
mod = 998244353
n = int(input())
*a, = map(int, input().split())
*b, = map(int, input().split())
m = 3000
dp = np.ones(m + 1,dtype=int)
for i in range(n):
    nx = np.zeros(m + 1,dtype=int)
    nx[a[i]:b[i]+1] = dp[a[i]:b[i]+1]###www
    dp = nx
    dp = np.cumsum(dp)
    dp %= mod
print(dp[m])

 

※ 생각해볼 거리

DP와 분할 정복은 무엇이 다른가

DP와 DFS, DFS 가지치기, 백트래킹과 무엇이 다른가

 

2. Codeforces Round #748 (Div.3) (D1번 문제) 

문제

https://codeforces.com/contest/1593/problem/D1

 

풀이

각 수에서 k 를 몇 번씩 (숫자마다 몇 번 뺄지는 마음대로 해도 된다) 빼서 계산했을 때 최종적인 숫자가 같게 나오려면 최대 얼마나 큰 k 를 쓰면 되는지 구해야한다.

숫자들에서 일정한 수를 뺀다는 것은 숫자가 공통된 수가 더해져있다는 것을 의미한다.

 

1 = 1 + 2*0

5 = 1 + 2*2

3 = 1 + 2*1

 

이렇게 공통의 2 라는 k 가 더해져있는 것으로 보면 된다. 그러므로 더해져있는 1을 제거하기 위해 바로 옆에 있는 숫자들끼리 빼든지, 첫번째로 들어온 거를 빼든지 하여튼 두 수 끼리 빼기만 하면 뒤에 2 * 무언가 형태로 남게 되니까 이걸로 최대 공약수를 찾으면 된다.

 

최대공약수는 유클리드 호제법을 쓰면 엄청 빠르고 쉽게 찾을 수 있다.

 

코드

def gcd(a, b):
    return gcd(b, a%b) if b else a

for _ in range(int(input())):
    N = int(input())
    A = list(map(int, input().split()))

    g = 0
    for i in range(1, N):
        d = A[i] - A[0] # i-1 수와 빼도 상관 없음
        if d < 0: d = -d # abs
        g = gcd(d, g)
    if g == 0:
        g= -1
    print(g)

 

※ 생각해볼 거리

한 수를 잡아서 차이를 구하든, 바로 옆 수와 차이를 구하든 아무 상관 없다는 증명이 가능한가?

 

PPT 파일로 정리한 자료

알고리즘 대회_2021_10_Week3.pptx

0.41MB