20200227 알고리즘

1. K번째 약수

어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다. 6을 예로 들면

6÷1=6…0 6÷2=3…0 6÷3=2…0 6÷4=1…2 6÷5=1…1 6÷6=1…0

그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다. 두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

▣ 입력설명 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

▣ 출력설명 첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 -1을 출력하시오.

▣ 입력예제 1

6 3

▣ 출력예제 1

3

Solution

def solution(n):
  cnt = 0
  for i in range(1, n+1):
    if n % i == 0:
      cnt += 1
    if cnt == k:
      print(i):
      break
  else:
    print(-1)

2. K번째 작은수

N개의 숫자로 이루어진 숫자열이 주어지면 해당 숫자열중에서 s번째부터 e번째 까지의 수 중 k번째로 작은 수를 출력하는 프로그램을 작성하세요.

▣ 입력설명 첫 번째 줄에 테스트 케이스 T(1<=T<=10)이 주어집니다. 각 케이스별 첫 번째 줄은 자연수 N(5<=N<=500), s, e, k가 차례로 주어진다. 두 번째 줄에 N개의 숫자가 차례로 주어진다.

▣ 출력설명 각 케이스별 k번째 수를 아래 출력예제와 같이 출력하세요.

▣ 입력예제 1 2 6253 527389 15 3 10 3

4 15 8 16 6 6 17 3 10 11 18 7 14 7 15

▣ 출력예제 1

• 1 7
• 2 6

Solution

import sys
sys.stdin = open("input2.txt", "rt")
T = int(input())
for t in range(T):
    n, s, e, k = map(int, input().split())
    a = list(map(int, input().split()))
    a = a[s-1:e+1]
    a.sort()
    print(a[k-1])

3. K번째 큰 수

현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다. 현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려 고 합니다. 3장을 뽑을 수 있는 모든 경우를 기록합니다. 기록한 값 중 K번째로 큰 수를 출력 하는 프로그램을 작성하세요.

만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19…이고 K값이 3이라면 K번째 큰 값 은 22입니다.

▣ 입력설명 첫 줄에 자연수 N(3<=N<=100)과 K(1<=K<=50) 입력되고, 그 다음 줄에 N개의 카드값이 입력 된다.

▣ 출력설명 첫 줄에 K번째 수를 출력합니다. K번째 수는 반드시 존재합니다.

▣ 입력예제 1 10 3 13 15 34 23 45 65 33 11 26 42

▣ 출력예제 1

143

Solution

import sys
sys.stdin = open("input3.txt", "rt")
n, k = map(int, input().split())
a = list(map(int, input().split()))

res = set()
for i in range(n):
    for j in range(i+1, n):
        for m in range(j+1, n):
            res.add(a[i] + a[j] + a[m])
res = list(res)
res.sort(reverse=True)
print(res[k-1])

4. 대표값

N명의 학생의 수학성적이 주어집니다. N명의 학생들의 평균(소수 첫째자리 반올림)을 구하고, N명의 학생 중 평균에 가장 가까운 학생은 몇 번째 학생인지 출력하는 프로그램을 작성하세 요. 답이 2개일 경우 성적이 높은 학생의 번호를 출력하세요. 만약 답이 되는 점수가 여러 개일 경우 번호가 빠른 학생의 번호를 답으로 한다.

▣ 입력설명 첫줄에 자연수 N(5<=N<=100)이 주어지고, 두 번째 줄에는 N개의 자연수가 주어진다. 학생의 번호는 앞에서부터 1로 시작해서 N까지이다.

▣ 출력설명 첫줄에 평균과 평균에 가장 가까운 학생의 번호를 출력한다. 평균은 소수 첫째 자리에서 반올림합니다.

▣ 입력예제 1 10 65 73 66 87 92 67 55 79 75 80

▣ 출력예제 1

74 9

Solution

import sys
sys.stdin = open("input4.txt", "rt")
n = int(input())
scores = list(map(int, input().split()))

avg = round(sum(scores) / n)
score = 0
min = 2147000000

for i, x in enumerate(scores):
    dif = abs(x - avg)
    if min > dif:
        min = dif
        score = x
        res = i+1
    elif min == dif:
        if score < x:
            score = x
            res = i+1

print(avg, res)

5. 정다면체

두 개의 정 N면체와 정 M면체의 두 개의 주사위를 던져서 나올 수 있는 눈의 합 중 가장 확 률이 높은 숫자를 출력하는 프로그램을 작성하세요. 정답이 여러 개일 경우 오름차순으로 출력합니다.

▣ 입력설명 첫 번째 줄에는 자연수 N과 M이 주어집니다. N과 M은 4, 6, 8, 12, 20 중의 하나입니다.

▣ 출력설명 첫 번째 줄에 답을 출력합니다.

▣ 입력예제 1

4 6

▣ 출력예제 1

5 6 7

Solution

import sys
sys.stdin = open("input5.txt", "rt")

n, m = map(int, input().split())
a = [0] * (n + m + 1)
max = -2147000000

for i in range(1, n+1):
    for m in range(1, m+1):
        a[i+m] += 1

for j in range(1, n+m+1):
    if a[j] > max:
        max = a[j]

for i in range(1, n+m+1):
    if a[i] == max:
        print(i, end=' ')