20200319 알고리즘
1. 수들의 조합
N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수 는 몇 개가 있는지 출력하는 프로그램을 작성하세요. 예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12 2+4+12로 2가지가 있습니다.
▣ 입력설명 첫줄에 정수의 개수 N(3<=N<=20)과 임의의 정수 K(K<=N)가 주어지고, 두 번째 줄에는 N개의 정수가 주어진다. 세 번째 줄에 M이 주어집니다.
▣ 출력설명 총 가지수를 출력합니다.
▣ 입력예제 1
5 3
2 4 5 8 12
6▣ 출력예제 1
2
Solution
import sys
sys.stdin = open("input55.txt", "rt")
def DFS(L, s, sum):
global cnt
if L == m:
if sum % div == 0:
cnt += 1
return
else:
for i in range(s, n):
DFS(L + 1, i + 1, sum + a[i])
if __name__ == "__main__":
n, m = map(int, input().split())
a = list(map(int, input().split()))
div = int(input())
cnt = 0
DFS(0, 0, 0)
print(cnt)2. 인접 행렬
아래 그림과 같은 그래프 정보를 인접행렬로 표현해보세요.
▣ 입력설명 첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보와 거리비용이 주어진다.
▣ 출력설명
인접행렬을 출력하세요.
▣ 입력예제 1
6 9
1 2 7
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5▣ 출력예제 1
0 7 4 0 0 0
2 0 5 0 5 0
0 0 0 5 0 0
0 2 0 0 5 0
0 0 0 0 0 0
0 0 0 5 0 0Solution
import sys
sys.stdin = open("input57.txt", "rt")
if __name__ == '__main__':
n, m = map(int, input().split())
a = [[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
p, q, r = map(int, input().split())
a[p][q] = r
for i in range(1, n+1):
for j in range(1, n+1):
print(a[i][j], end=' ')
print()3. 수들의 합
문제
서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?
입력
첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.
출력
첫째 줄에 자연수 N의 최댓값을 출력한다.
Soltuion
if __name__ == '__main__':
n = int(input())
cnt = 1
while True:
n -= cnt
if n > cnt:
cnt += 1
else:
break
print(cnt)4. 경로 탐색
방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하세요
▣ 입력설명 첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.
▣ 출력설명 총 가지수를 출력한다.
▣ 입력예제
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5▣ 출력예제 1
6
Solution
import sys
sys.stdin = open("input58.txt", "rt")
def DFS(E):
global cnt
if E == n:
cnt += 1
for v in path:
print(v, end=' ')
print()
else:
for i in range(1, n+1):
if g[E][i] == 1 and ch[i] == 0:
ch[i] = 1
path.append(i)
DFS(i)
path.pop()
ch[i] = 0
if __name__ == '__main__':
n, m = map(int, input().split())
g = [[0]*(n+1) for _ in range(n+1)]
ch = [0]*(n+1)
for _ in range(m):
p, q = map(int, input().split())
g[p][q] = 1
cnt = 0
path = list()
ch[1] = 1
path.append(1)
DFS(1)
print(cnt)5. 최대점수 구하기
이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)
▣ 입력설명 첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다. 두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.
▣ 출력설명 첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.
▣ 입력예제 1
5 20
10 5
25 12
15 8
6 3
7 4▣ 출력예제 1
41
Solution
import sys
sys.stdin = open("input59.txt", "rt")
def DFS(L, score_sum, time_sum):
global max
if time_sum > m:
return
if L == n:
if max < score_sum:
max = score_sum
else:
DFS(L+1, score_sum + scores[L], time_sum + times[L])
DFS(L+1, score_sum, time_sum)
if __name__ == '__main__':
n, m = map(int, input().split())
scores = list()
times = list()
for _ in range(n):
s, t = map(int, input().split())
scores.append(s)
times.append(t)
max = -2147000000
DFS(0, 0, 0)
print(max)
![[HongDongUk]](/static/a60d793d17c3aad0361c9192a3b51381/a12fc/profile.png)