[코드포스] Codeforces Round #678 (Div. 2)

대회 링크: codeforces.com/contest/1436

A번 문제: codeforces.com/contest/1436/problem/A

 

  아래 식이 의미하는 내용은 a1 + a2 + ... + an이다. 시그마가 중첩되어 작성되어 있어서 헷갈릴 수 있지만, 식을 나열해보면 그렇다. 다시 말해 그냥 모든 원소의 합이 M과 같다면 "YES", M과 다르다면 "NO"를 출력하면 된다.

 

 

for _ in range(int(input())):
    n, m = map(int, input().split())
    data = list(map(int, input().split()))

    # 모든 원소의 합이 M인 경우 "YES" 출력
    if sum(data) == m:
        print("YES")
    else:
        print("NO")

 

B번 문제: codeforces.com/contest/1436/problem/B

 

  이 문제는 원소로 0을 사용할 수 있다는 점을 생각하면 매우 쉽다. 1을 2개 쓰고, 나머지를 0으로 채우면 된다. 이후에 각 줄마다 시프트(shift)를 하면서 출력하면 된다. 예를 들어 N = 4일 때는 다음과 같이 만들면 된다.

 

for _ in range(int(input())):
    n = int(input())
    arr = [1, 1] + [0] * (n - 2)
    arr = arr + arr

    for i in range(n):
        for j in range(i, n + i):
            print(arr[j], end=' ')
        print()

 

  사실 나는 이 문제를 푸는 당시에는 N이 100 이하라서 에라토스테네스의 체를 이용해 N = 100까지의 모든 경우에 대하여 사전에 계산하는 방식을 이용했다. 아무튼 제일 쉬운 방법은 그냥 0과 1로 배열을 채우는 것이다.

 

C번 문제: codeforces.com/contest/1436/problem/C

 

  예시로 n = 6, x = 3, pos = 1이라고 해보자. 그러면 다음과 같이 3은 항상 인덱스(index) 1에 위치할 것이다. 이때 주어진 알고리즘에 맞게 그대로 시뮬레이션하면 된다. 일단 시작 단계는 다음과 같을 것이다.

 

 

  이후에 중간점(mid)을 확인한다. 향후 중간점의 왼쪽 부분을 탐색해야 하므로, 중간점(mid)에 위치한 값은 x보다 큰 값이 되어야 한다.

 

 

  이후에 마찬가지로 중간점(mid)을 확인하는데, x를 찾은 것을 알 수 있다. 여기에서 중요한 점은 주어진 알고리즘에 따르면 여기에서 알고리즘을 종료하지 않고 계속해서 탐색을 진행한다는 것이다. 이 부분을 놓치면 오답 판정을 받게 된다.

 

 

  다음 단계에서도 중간점(mid)을 확인한다. 여기에서 중간점은 마찬가지로 x보다 큰 수가 되어야 한다.

 

 

  이 예시에서의 정답은 (3보다 큰 수의 개수에서 2개를 뽑는 순열의 수) * 3!이 된다. 다시 말해 정답은 36이다. 이러한 원리를 그대로 코드로 옮겨 구현하면 다음과 같다.

 

MOD = int(1e9 + 7)

n, x, pos = map(int, input().split())

under_cnt = x - 1
over_cnt = n - x

under = 0
over = 0
 
left = 0
right = n

while left < right:
    middle = (left + right) // 2
    if middle < pos:
        left = middle + 1
        under += 1
    elif middle > pos:
        right = middle
        over += 1
    # (핵심) middle == pos일 때에도 멈추지 않음
    else:
        left = middle + 1

if under > under_cnt or over_cnt < over:
    print(0)
else:
    answer = 1
    # Permutation(under_cnt, under)
    for i in range(under):
        answer = (answer * (under_cnt - i)) % MOD
    # Permutation(over_cnt, over)
    for i in range(over):
        answer = (answer * (over_cnt - i)) % MOD
    # 남은 수들에 대해서도 Permutation 돌리면 정답
    for i in range(1, n - under - over):
        answer = (answer * i) % MOD
    print(answer)