41일차 문제

문제풀이

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

예제 입력 1
3
2 2
1 5
13 29

예제 출력 1
1
5

import math
a = int(input())
for _ in range(a):
    b, c = map(int, input().split())
    d = math.factorial(c) // (math.factorial(b) * math.factorial(c - b))
    print(d)

c개의 지역에 b개의 다리를 놓을 수 있는 경우의 수를 구해야 함으로
cCb 으로 표현할 수 있고 이는 c! 을 (c-b)!b! 으로 나눈 값이 된다.

두번째

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

예제 입력 1
5
1 1 1 6 0
2 7 8 3 1

예제 출력 1
18

a = int(input())
b = list(map(int, input().split()))
c = list(map(int, input().split()))
re = 0
for i in range(a):
  re += b.pop(b.index(min(b))) * c.pop(c.index(max(c)))
print(re)

b의 최솟값을 c의 최대값과 곱해주면서 pop을 통해서 그 리스트를 제거해주면서 리스트의 길이만큼 반복한다.